Merge implementation with predicate

I study algorythms carefully during last two weeks and as you probably know, many algorythm tasks require implementation of sorting procedure. There is a huge amount of various sorting algorythms, such as Quick Sort, Heap Sort and so on. But one of the easiest to implement is a Merge Sort. You can find its description somewhere. I implemented it several times - for ascending sorting, for descending sorting and so on, so finally i take time to implement it with any predicate you like. Here is an implementation:

There is one class SortManager with method Sort, that calls itself recursively on input parts:

 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 namespace MergePredicate  
 {  
      public class SortManager  
      {  
           public int[] Sort(int[] data, Func<int, int, bool> predicate)  
           {  
                if (data.Length <= 1) return data;  
                decimal mediana = data.Length / 2;  
                // left part of our input for first recursion call  
                int[] leftPart = new int[(int)Math.Floor(mediana)];  
                // right part  
                int[] rightPart = new int[data.Length - (int)Math.Floor(mediana)];  
                // fill left part with data  
                for (int i = 0; i < leftPart.Length; i++)  
                {  
                     leftPart[i] = data[i];  
                }  
                // fill right part  
                for (int i = leftPart.Length; i < data.Length; i++)  
                {  
                     rightPart[i - leftPart.Length] = data[i];  
                }  
                // sort both parts  
                int[] leftSorted = Sort(leftPart, predicate);  
                int[] rightSorted = Sort(rightPart, predicate);  
                return MergeByPredicate(leftSorted, rightSorted, predicate);  
           }  
           /// <summary>  
           /// Main procedure - merge both sorted arrays in one  
           /// </summary>  
           /// <param name="leftSorted"></param>  
           /// <param name="rightSorted"></param>  
           /// <param name="predicate"></param>  
           /// <returns></returns>  
           public int[] MergeByPredicate(int[] leftSorted, int[] rightSorted, Func<int, int, bool> predicate)  
           {  
                // returned merged array  
                int[] data = new int[leftSorted.Length + rightSorted.Length];  
                // cursors over both parts  
                int i = 0;  
                int j = 0;  
                while (i + j < data.Length)  
                {  
                     // we are in the end of right part  
                     if (j == rightSorted.Length)  
                     {  
                          while (i < leftSorted.Length)  
                          {  
                               data[i + j] = leftSorted[i];  
                               i++;  
                          }  
                     }  
                     // or in the end of left part  
                     if (i == leftSorted.Length)  
                     {  
                          if (j < rightSorted.Length)  
                          {  
                               data[i + j] = rightSorted[j];  
                               j++;  
                          }  
                     }  
                     // left part of both conditions we need not to get out of the bound of data  
                     while (i < leftSorted.Length && predicate(leftSorted[i], rightSorted[j]))  
                     {  
                          data[i + j] = leftSorted[i];  
                          i++;  
                     }  
                     while (j < rightSorted.Length && i < leftSorted.Length && predicate(rightSorted[j], leftSorted[i]))  
                     {  
                          data[i + j] = rightSorted[j];  
                          j++;  
                     }  
                }  
                return data;  
           }  
      }  
 }  

I also added some tests if you want to see it's working. I use NUnit as Test Tool cause i have no Visual Studio Testing tool at home. Last note: be carefull about predicate to compare values. It should work as if predicate(a, b) == false then predicate(b, a) == true so dont pass predicate like (a, b) => a < b cause it won't pass condition if a = b (cause a < b == false and b < a == false) instead use (a, b) => a <= b The third test method provides a predicate to separate array on odd and non-odd numbers, for you to evaluate the power of predicate merge ;-)

 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 using NUnit;  
 using NUnit.Framework;  
 using MergePredicate;  
 namespace MergePredicate.Fixture  
 {  
      public class MergePredicateTest  
      {  
           [Test]  
           public void TestDescendingSort()  
           {  
                SortManager manager = new SortManager();  
                var data = new [] { 3, 12, 6, 9, 43, 1, 33, 23, 12, 38, 7, 19 };  
                Func<int, int, bool> predicate = (a, b) => a <= b;  
                var output = manager.Sort(data, predicate);  
                checkSorting(data, output, predicate);  
           }  
           [Test]  
           public void TestAscendingSort()  
           {  
                SortManager manager = new SortManager();  
                var data = new[] { 3, 12, 6, 9, 43, 1, 33, 23, 12, 38, 7, 19 };  
                Func<int, int, bool> predicate = (a, b) => a >= b;  
                var output = manager.Sort(data, predicate);  
                checkSorting(data, output, predicate);  
           }  
           [Test]  
           public void TestOddnessSort()  
           {  
                SortManager manager = new SortManager();  
                var data = new[] { 3, 12, 6, 9, 43, 1, 33, 23, 12, 38, 7, 19 };  
                Func<int, int, bool> predicate =  
                     (a, b) =>  
                     {  
                          if (a % 2 != 0 && b % 2 == 0) return false;  
                          return true;  
                     };  
                var output = manager.Sort(data, predicate);  
                checkSorting(data, output, predicate);  
           }  
           void checkSorting(int[] data, int[] sortedData, Func<int, int, bool> predicate)  
           {  
                Assert.AreEqual(data.Length, sortedData.Length);  
                if (sortedData.Length > 1)  
                {  
                     for (int i = 1; i < sortedData.Length; i++)  
                     {  
                          Assert.IsTrue(predicate(sortedData[i - 1], sortedData[i]));  
                     }  
                }  
                foreach (int sorted in sortedData)  
                {  
                     bool sortedIsInInitial = false;  
                     foreach (int initial in data)  
                     {  
                          if (sorted == initial)  
                          {  
                               sortedIsInInitial = true;  
                               break;  
                          }  
                     }  
                     Assert.IsTrue(sortedIsInInitial);  
                }  
           }  
      }  
 }