Merge sort in C#

Merge sort - overview

Merge sort is a comparison based divide-and-conquer sorting algoritm. It was invented by John von Neumann in 1945. It is also a stable algorithm, which means that the order of equal elements in the input array will be kept so that it is the same after sorting.

The algorithm is based on the fact that two ordered arrays can be merged pretty quickly and easy. One just loops through the two arrays in parallel och copies the smallest value of the two arrays into a third array. The algorithm then uses recursive divide-and-conquer methodology to get the sorting done.

Description of the merge sort algorithm

The algorithm works like this:

1. The unsorted input array is recursively divided into n subarrays containing one element each. A list with only 1 element is considered to be sorted.
2. The subarrays are merged to produce new sorted subarrays until there is only one array left.

Computational complexity

In each recursion level merging is performed. Since merging is a linear operation, at each level we are doing O(n) work.

In each recursive step we are dividing the size of the input in half. Therefore there will be O(log n) recursive calls.

The number of recursive calls multiplied with the work at each level thus gives us the total complexity of O(n log n).

Example of an implementation of merge sort in C#

    private void SortArrayWithMergeSort()
    {
        int[] array = { 7, 5, 17, 3, 1 };

        int low = 0;
        int hi = array.Length - 1;

        MergeSort(array, low, hi);

        // PrintResult(array);
    }

    public void MergeSort(int[] array, int low, int hi)
    {
        if (hi - low <= 0)
        {
            return;
        }

        int mid = (low + hi) / 2;
        MergeSort(array, low, mid);
        MergeSort(array, mid + 1, hi);
        Merge(array, low, mid + 1, hi);
    }

    private void Merge(int[] array, int low, int mid, int hi)
    {
        int[] temp = new int[array.Length];
        int tempCount = low;
        int i = low;
        int j = mid;

        while (i < mid && j <= hi)
        {
            if (array[i] <= array[j])
            {
                temp[tempCount++] = array[i++];
            }
            else
            {
                temp[tempCount++] = array[j++];
            }
        }

        while (i < mid)
        {
            temp[tempCount++] = array[i++];
        }

        while (j <= hi)
        {
            temp[tempCount++] = array[j++];
        }

        for (int k = low; k <= hi; k++)
        {
            array[k] = temp[k];
        }   
    }