Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
C# interpretation of the top-down implementation of Merge Sort from Wikipedia: http://en.wikipedia.org/wiki/Merge_sort
using System;
using System.Collections.Generic;
using System.Linq;
/* Write a program that sorts an array of integers
* using the merge sort algorithm (find it in Wikipedia). */
class MergeSortAlgorithm
{
public static int[] MergeSort(int[] array)
{
// If list size is 0 (empty) or 1, consider it sorted and return it
// (using less than or equal prevents infinite recursion for a zero length array).
if (array.Length <= 1)
{
return array;
}
// Else list size is > 1, so split the list into two sublists.
int middleIndex = (array.Length) / 2;
int[] left = new int[middleIndex];
int[] right = new int[array.Length - middleIndex];
Array.Copy(array, left, middleIndex);
Array.Copy(array, middleIndex, right, 0, right.Length);
// Recursively call MergeSort() to further split each sublist
// until sublist size is 1.
left = MergeSort(left);
right = MergeSort(right);
// Merge the sublists returned from prior calls to MergeSort()
// and return the resulting merged sublist.
return Merge(left, right);
}
public static int[] Merge(int[] left, int[] right)
{
// Convert the input arrays to lists, which gives more flexibility
// and the option to resize the arrays dynamically.
List<int> leftList = left.OfType<int>().ToList();
List<int> rightList = right.OfType<int>().ToList();
List<int> resultList = new List<int>();
// While the sublist are not empty merge them repeatedly to produce new sublists
// until there is only 1 sublist remaining. This will be the sorted list.
while (leftList.Count > 0 || rightList.Count > 0)
{
if (leftList.Count > 0 && rightList.Count > 0)
{
// Compare the 2 lists, append the smaller element to the result list
// and remove it from the original list.
if (leftList[0] <= rightList[0])
{
resultList.Add(leftList[0]);
leftList.RemoveAt(0);
}
else
{
resultList.Add(rightList[0]);
rightList.RemoveAt(0);
}
}
else if (leftList.Count > 0)
{
resultList.Add(leftList[0]);
leftList.RemoveAt(0);
}
else if (rightList.Count > 0)
{
resultList.Add(rightList[0]);
rightList.RemoveAt(0);
}
}
// Convert the resulting list back to a static array
int[] result = resultList.ToArray();
return result;
}
static void Main()
{
int[] array = new int[] { 5, 2, 6, 4, 7, 10, 1, 9, 3, 8 };
array = MergeSort(array);
// Print the sorted list
for (int index = 0; index < array.Length; index++)
{
Console.WriteLine("element[{0}] = {1}", index, array[index]);
}
Console.WriteLine();
}
}
@Zerophase

This comment has been minimized.

Copy link

commented Sep 19, 2015

I wrote what I believe is a faster merge sort, with your code as reference. Interested in it?

@TheBestManInTheWorld

This comment has been minimized.

Copy link

commented Feb 11, 2016

It's a hard topic but you described that very good and after a couple of minutes a understood how it works.
Thanks. 👍
:)

@lluuiissoo

This comment has been minimized.

Copy link

commented Aug 5, 2016

Great work! Very useful and concise.

@jaykodeveloper

This comment has been minimized.

Copy link

commented Jan 29, 2017

It is very helpful to understand merge sort in c#. Thank you!

@emridul

This comment has been minimized.

Copy link

commented Jul 20, 2017

Found useful post on Merge Sort with C# code
https://15to20minutes.com/2017/07/19/merge-sort-c-example/

@shilsmarty

This comment has been minimized.

Copy link

commented Aug 6, 2017

Thanks , perfectly right implementation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.