MergeSort algorithm in c#

Question

I wrote below code for Merge Class :

class Merge
{

    public static void sort(IComparable[] a)
    {
        sort(a, 0, a.Length);
    }

    public static void sort(IComparable[] a, int low, int high)
    {
        int N = high - low;
        if (N <= 1)
            return;

        int mid = low + N / 2;

        sort(a, low, mid);
        sort(a, mid, high);

        IComparable[] aux = new IComparable[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++)
        {
            if (i == mid) aux[k] = a[j++];
            else if (j == high) aux[k] = a[i++];
            else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
            else aux[k] = a[i++];
        }

        for (int k = 0; k < N; k++)
        {
            a[low + k] = aux[k];
        }
    }

    private static Boolean isSorted(IComparable[] a)
    {
        for (int i = 1; i < a.Length; i++)
            if (a[i].CompareTo(a[i - 1]) < 0) return false;
        return true;
    }

}

And below code is Implementation. i thought below code should't be wrong! but it's does't compile...

class Program
{
    static void Main(string[] args)
    {
    Merge ms = new Merge();

    Double[] MyArray = { 80,10,52,7,36,7,67,1,8,54 };
    Console.WriteLine("first array is: \n");
    for (int k = 0; k < MyArray.Length; k++)
    {
        Console.Write(MyArray[k]);
        if (k<9)
           Console.Write(" , ");
    }
    ms.sort(MyArray);  // Error is here. Does't compile !!!
    Console.WriteLine("\n");
    Console.WriteLine("\nsorted array is: \n ");
    for (int k = 0; k < MyArray.Length; k++)
    {
        Console.Write(MyArray[k]);
        if (k<9)
           Console.Write(" , ");
    }
    Console.ReadLine();
    }
}

It's does't compile. Error is in ms.sort(MyArray);. What am i doing wrong? Please lead me...

Regards

Answer 1

There are two problems with this code:

1. The signature doesn't match, IComparable[] is not directly compatible with double[] in this case
2. You cannot call the sort method through the instance directly

The minimal amount of changes to fix this would be to make the method generic, and call Merge.sort instead of ms.sort.

Here's how I would implement sort:

public static void sort<T>(T[] a)
    where T : IComparable<T>
{
    sort(a, 0, a.Length);
}

public static void sort<T>(T[] a, int low, int high)
    where T : IComparable<T>
{
    int N = high - low;
    if (N <= 1)
        return;

    int mid = low + N / 2;

    sort(a, low, mid);
    sort(a, mid, high);

    T[] aux = new T[N];
    int i = low, j = mid;
    for (int k = 0; k < N; k++)
    {
        if (i == mid) aux[k] = a[j++];
        else if (j == high) aux[k] = a[i++];
        else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
        else aux[k] = a[i++];
    }

    for (int k = 0; k < N; k++)
    {
        a[low + k] = aux[k];
    }
}

Note that I changed to using T instead of IComparable, and added a constraint saying we need a T that implements IComparable<T>.

Additionally, change your call from this:

ms.sort(...);

to this:

Merge.sort(...);