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

Try calling MyArray.sort(); never mind - I thought it was an extension method... If you change the signature appropriately - add the "this" keyword, you can extend the array object. — GKlesczewski
– GKlesczewski, Commented Apr 5, 2013 at 13:58
I've two errors. first: Error 1 The best overloaded method match for 'MergeSort.Merge.sort(System.IComparable[])' has some invalid arguments c:\users\hamed\documents\visual studio 2010\Projects\MergeSort\MergeSort\Program.cs 22 9 MergeSort and second is Error 2 Argument 1: cannot convert from 'double[]' to 'System.IComparable[]' c:\users\hamed\documents\visual studio 2010\Projects\MergeSort\MergeSort\Program.cs 22 17 MergeSort — Hamed Kamrava
– Hamed Kamrava, Commented Apr 5, 2013 at 13:58

Lasse V. Karlsen · Accepted Answer · 2013-04-05 14:03:13Z

There are two problems with this code:

The signature doesn't match, IComparable[] is not directly compatible with double[] in this case
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(...);

Amit Sinha · Accepted Answer · 2013-12-29 11:52:36Z

    //merge sort recurcive

    public void MergeSort(int[] input,int startIndex,int endIndex)
    {
        int mid;

        if (endIndex > startIndex)
        {
            mid = (endIndex + startIndex) / 2;
            MergeSort(input, startIndex, mid);
            MergeSort(input, (mid + 1), endIndex);
            Merge(input, startIndex, (mid + 1), endIndex);
        }
    }

    public void Merge(int[] input, int left, int mid, int right)
    {
        //Merge procedure takes theta(n) time
        int[] temp = new int[input.Length];
        int i, leftEnd,lengthOfInput,tmpPos;
        leftEnd = mid - 1;
        tmpPos = left;
        lengthOfInput = right - left + 1;

        //selecting smaller element from left sorted array or right sorted array and placing them in temp array.
        while ((left <= leftEnd) && (mid <= right))
        {
            if (input[left] <= input[mid])
            {
                temp[tmpPos++] = input[left++];
            }
            else
            { 
                temp[tmpPos++]=input[mid++];
            }
        }
        //placing remaining element in temp from left sorted array
        while (left <= leftEnd)
        {
            temp[tmpPos++] = input[left++];
        }

        //placing remaining element in temp from right sorted array
        while (mid <= right)
        {
            temp[tmpPos++] = input[mid++];
        }

        //placing temp array to input
        for (i = 0; i < lengthOfInput;i++ )
        {
            input[right]=temp[right];
            right--;
        }
    }

     int[] input3 = { 22, 4, 6, 0, 9, 12, 156, 86,99};
     MergeSort(input3, 0, input3.Length - 1);
        for (int i = 0; i < input3.Length; i++)
            Console.Write(input3[i]+", ");
        Console.WriteLine("");

Thanks for commenting the code. Makes it easier to understand.

Matt Burland · Accepted Answer · 2013-04-05 13:58:30Z

2

Your sort method is static, you shouldn't call it from an instance of your class.

You should call it like this:

Merge.sort(MyArray);

not:

ms.sort(MyArray);

In fact, since you Merge class has no instance methods, there is no point creating an instance of it and you should probably just mark the whole class as static.

answered Apr 5, 2013 at 13:58

Matt Burland

45.3k18 gold badges110 silver badges182 bronze badges

1 Comment

Matt Burland Over a year ago

@HamedKamrava: See @LasseVKarlsen's answer. You have another problem too in that double[] can't be automatically converted to IComparable[].

Arun Kumar · Accepted Answer · 2020-05-16 14:29:25Z

A simple C# code to do merge sort

using System;

namespace MergeSort
{
    class Program
    {
        static void Main(string[] args)
        {            
            int[] arInt = { 6, 4, 2, 8, 4, 8, 11, 1, 7, 4, 13, 5, 45, -1, 0, -7, 56, 10, 57 };
            var sortedIntAr = GenericMergeSort<int>.Sort(arInt);

            string[] arStr = { "Here", "Is", "A", "Cat", "Really", "Fast", "And", "Clever" };
            var sortedStrAr = GenericMergeSort<string>.Sort(arStr);

            Console.WriteLine(String.Join(',', sortedIntAr));
            Console.WriteLine(String.Join(',', sortedStrAr));

            Console.ReadLine();
        }

    }
    class GenericMergeSort<T> where T : IComparable
    {
        public static T[] Sort(T[] ar)
        {
            var arLen = ar.Length;
            if (arLen < 2)
                return ar;

            var arL = ar.AsSpan(0..(arLen / 2)).ToArray();
            var arR = ar.AsSpan((arLen / 2)..arLen).ToArray();

            arL = Sort(arL);
            arR = Sort(arR);

            return Merge(arL, arR);
        }

        private static T[] Merge(T[] arL, T[] arR)
        {
            var mergedArray = new T[arL.Length + arR.Length];
            int iM = 0, iL = 0, iR = 0;

            while (iL < arL.Length || iR < arR.Length)
            {
                mergedArray[iM++] = iL < arL.Length && (iR > arR.Length - 1 || arL[iL].CompareTo(arR[iR]) < 0)
                                    ? arL[iL++] : arR[iR++];
            }
            return mergedArray;
        }
    }
}

Here is the output

-7,-1,0,1,2,4,4,4,5,6,7,8,8,10,11,13,45,56,57

A,And,Cat,Clever,Fast,Here,Is,Really

Komal12 · Accepted Answer · 2018-03-09 05:08:59Z

public static int[] mergeSort(int[] ar)
{
    Func<int[], int[]> firstHalf = (array) =>
     {
         return array.Take((array.Length + 1) / 2).ToArray();
     };

    Func<int[], int[]> secondHalf = (array) =>
    {
        return array.Skip((array.Length + 1) / 2).ToArray();                
    };

    Func<int[], int[], int[]> mergeSortedArrays = (ar1, ar2) =>
    {
        int[] mergedArray = new int[ar1.Length + ar2.Length];

        int i1 = 0, i2 = 0, currentMin;

        while (i1 < ar1.Length || i2 < ar2.Length)
        {
            if (i1 < ar1.Length && i2 < ar2.Length)
            {
                if (ar1[i1] < ar2[i2])
                {
                    currentMin = ar1[i1];
                    i1++;
                }
                else
                {
                    currentMin = ar2[i2];
                    i2++;
                }
            }
            else if (i1 < ar1.Length)
            {
                currentMin = ar1[i1];
                i1++;
            }
            else
            {
                currentMin = ar2[i2];
                i2++;
            }
            mergedArray[i1 + i2 - 1] = currentMin;
        }
        return mergedArray;
    };

    int[] half1 = firstHalf(ar); //always /geq than half2
    int[] half2 = secondHalf(ar);

    if (half1.Length < 2)
        return mergeSortedArrays(half1, half2);
    else
        return mergeSortedArrays(mergeSort(half1), mergeSort(half2));

}

Saif Ur Rehman · Accepted Answer · 2020-10-02 10:58:44Z

A simple C# merge sort.

using System.Collections.Generic;

namespace Sort
{
    public class MergeSort
    {
        public static List<int> mergeSort(List<int> list)
        {
            if (list.Count <= 1) return list;

            List<int> result;
            List<int> left = new List<int>();
            List<int> right = new List<int>();

            int midPoint = list.Count / 2;

            left.AddRange(list.GetRange(0, midPoint));
            right.AddRange(list.GetRange(midPoint, list.Count - midPoint));

            left = mergeSort(left);

            right = mergeSort(right);

            result = merge(left, right);
            return result;
        }

        //This method will be responsible for combining our two sorted arrays into one giant array
        public static List<int> merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>();

            int indexLeft = 0, indexRight = 0, indexResult = 0;
            while (indexLeft < left.Count || indexRight < right.Count)
            {
                //if both arrays have elements  
                if (indexLeft < left.Count && indexRight < right.Count)
                {
                    if (left[indexLeft] <= right[indexRight])
                    {
                        result.Add(left[indexLeft]);
                        indexLeft++;
                    }
                    else
                    {
                        result.Add(right[indexRight]);
                        indexRight++;
                    }
                }
                else if (indexLeft < left.Count)
                {
                    result.Add(left[indexLeft]);
                    indexLeft++;
                }
                else if (indexRight < right.Count)
                {
                    result.Add(right[indexRight]);
                    indexRight++;
                }
                indexResult++;
            }
            return result;
        }
    }
}

Collectives™ on Stack Overflow

MergeSort algorithm in c#

6 Answers 6

Comments

1 Comment

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

1 Comment

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related