RSS

Merge Sort in C#

21 Aug

A simple Merge Sort implementation using C#.

public static void MergeSort(int[] input, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;

        MergeSort(input, left, middle);
        MergeSort(input, middle + 1, right);

        //Merge
        int[] leftArray = new int[middle - left + 1];
        int[] rightArray = new int[right - middle];

        Array.Copy(input, left, leftArray, 0, middle - left + 1);
        Array.Copy(input, middle + 1, rightArray, 0, right - middle);

        int i = 0;
        int j = 0;
        for (int k = left; k < right + 1; k++)
        {
            if (i == leftArray.Length)
            {
                input[k] = rightArray[j];
                j++;
            }
            else if (j == rightArray.Length)
            {
                input[k] = leftArray[i];
                i++;
            }
            else if (leftArray[i] <= rightArray[j])
            {
                input[k] = leftArray[i];
                i++;
            }
            else
            {
                input[k] = rightArray[j];
                j++;
            }
        }
    }
}
Advertisements
 
3 Comments

Posted by on August 21, 2012 in Algorithm, C#

 

3 responses to “Merge Sort in C#

  1. Andrei

    September 10, 2013 at 12:47 AM

    Thanks

     
  2. Jonnie

    October 1, 2014 at 11:11 PM

    I am a struggling C# programming student. This is the simplest implementation of MergeSort I have found, but I am still having trouble understanding how it works exactly. Could you help me in understanding what the method is doing?

     
    • begeeben

      October 10, 2014 at 12:28 AM

      Hope you’d understood the idea by now. I should have named the arguments clearer and added some comments.

      ‘left’ is the leftmost index of the array, ‘right’ is the rightmost index.

      The whole idea is to divide an array into 2 recursively until it’s down to one or two elements. Then you compare them, put them into a 2 elements array in sorted order and compare it again with another sorted 2 elements array. Doing the comparison all the way to the top until you have the original array sorted.

      ex:

      1. [4, 2, 7, 5, 1, 8, 9, 6, 3]
      2. [4, 2, 7, 5] [1, 8, 9, 6, 3]
      3. [4, 2] [7, 5]
      4. [4] [2]
      5. [2, 4]
      6. [2, 4] [7] [5]
      7. [2, 4] [5, 7]
      8. [2, 4, 5, 7]

      and so on…

       

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: