Merge Sort – C# Example

Merge Sort
In data structure, there are may sorting algorithms like Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort etc. In this post we will discuss about Merge sort.

Core logic underneath Merge Sort

  • Keep dividing the unsorted list into sub-lists until each sub-list contains 1 element only (vacuously a list with only 1 element is considered as sorted list).
  • Now keep merging all these sub-lists to create new sorted sub-lists until there is only 1 sub-list remains containing all elements and this will be a sorted list.

Merge Sort is similar to Quick Sort as it also follows divide and conquer algorithm.
Most implementations of Merge sort consume additional space in memory, which may impact the performance.
Quick sort may perform better as it doesn’t consume additional space. However the performance may suffer if most of the elements are already sorted in array or list and pivot is not randomized appropriately (search for Quick sort for more clarity).
Merge sort has average complexity of O(nlog(n)). Merge sort algorithm divides input array in two almost equal parts, calls itself for the two parts recursively and then merges the two sorted parts. Refer below first image, it shows how recursively Merge sort algorithm divides array to to sub-arrays until it turns to sub-arrays with single element.

MergeSort1.PNG

Note: In above image you see 9/2= 4 (whereas in reality it should be 4.5), this because we are performing this operation in C# language where if we perform division operations on integer values you get result in integer only (you lose fraction part, we take this as an advantage for this example).
In above image, for better understanding I have used same variable names which are used in code snippet in this post so that you can relate better.
And below image shows how step by step merge of elements is done recursively by Merge sort algorithm.
MergeSort2

Below is the sample code in C# for Merge sort. Please refer comments between code lines to get more clarity.

public class MergeSort
{
//This number should be equal to or greater than length of array.
private const int ARRAY_LENGTH = 10;

/// <summary>
/// Call this method from Main() method to test Merge Sort
/// </summary>
public static void Test()
{

int[] items = { 10, 6, 4, 3, 8, 5, 7, 2, 1, 9 };

DivideAndSort(items, 0, items.Length - 1);

for (int i = 0; i < items.Length; i++)
Console.WriteLine(items[i]);
Console.Read();
}

/// <summary>
/// This method holds recursion calls to divide and sort array
/// </summary>
/// <param name="items"></param>
/// <param name="startIndex"></param>
/// <param name="endIndex"></param>
private static void DivideAndSort(int[] items, int startIndex, int endIndex)
{
int middleIndex;

if (endIndex > startIndex)
{
middleIndex = (endIndex + startIndex) / 2 + 1;

//Logically deviding array into two different sub-arrays.
//First subset of Array contains elements from starting index "leftIndex" to ending index "middleIndex - 1".
//Second subset of Array contains elements from starting index "middleIndex" to ending index "rightIndex".
//We are calling method DivideAndSort recursively here.
//In every method call, parameter values for startIndex and endIndex will vary,
//as every time we divide by 2 to calculate middleIndex.
DivideAndSort(items, startIndex, middleIndex - 1);
DivideAndSort(items, middleIndex, endIndex);

Merge(items, startIndex, endIndex);
}
}

/// <summary>
/// This method holds logic of sorting and merging parts of array
/// </summary>
/// <param name="items"></param>
/// <param name="startIndex">Starting index of sub-array (which is part of main array)</param>
/// <param name="endIndex">Ending index of sub-array (which is part of main array)</param>
private static void Merge(int[] items, int startIndex, int endIndex)
{
//This is temporary array to hold sorted elements
int[] tempItems = new int[ARRAY_LENGTH];

//Starting index of first subset of array
int firstSubArrayIndexVar = startIndex;
//Ending index of first subset of array
int firstSubArrayMaxIndex = (startIndex + endIndex) / 2;

//Starting index of second subset of array
int secondSubArrayIndexVar = (startIndex + endIndex) / 2 + 1;
//Ending index of second subset of array
int secondSubArrayMaxIndex = endIndex;

//Starting Index of temp Array
int startPosition = startIndex;

//Number of elements in both the subsets of Array before division
//Note: "itemCount" always total number of elements in "items" array
//As "items" array is logically divided into sub-arrays by considering different starting and ending indexes
int itemCount = (endIndex - startIndex + 1);

while ((firstSubArrayMaxIndex >= firstSubArrayIndexVar)
&& (secondSubArrayMaxIndex >= secondSubArrayIndexVar))
{
if (items[firstSubArrayIndexVar] <= items[secondSubArrayIndexVar])
{
tempItems[startPosition++] = items[firstSubArrayIndexVar++];
}
else
{
tempItems[startPosition++] = items[secondSubArrayIndexVar++];
}
}

while (firstSubArrayMaxIndex >= firstSubArrayIndexVar)
tempItems[startPosition++] = items[firstSubArrayIndexVar++];

while (secondSubArrayMaxIndex >= secondSubArrayIndexVar)
tempItems[startPosition++] = items[secondSubArrayIndexVar++];

int i = 0;
//Move elements of sorted temporary array to actual "items" array
while(i < itemCount)
{
items[secondSubArrayMaxIndex] = tempItems[secondSubArrayMaxIndex];
secondSubArrayMaxIndex--;
i++;
}
}
}

CommentRequest

Leave a Reply

Please log in using one of these methods to post your comment:

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