Recursive and Iterative Merge Sort Implementations

Curator's Note: In response to Stoimen Popov's Algorithm of the Week Post: Merge Sort, Chaker Nakhli pointed out that Stoimen only presented a recursive version of the merge sort algorithm. In this post, Chaker presents an iterative approach written in C#, but it can be easily converted to Java or any other language...


I find merge sort elegant and easy to implement and to understand for both iterative and recursive approaches. In this post I’ll share a quick (and probably dirty) iterative and recursive implementations of merge sort. Both versions share exactly the same merge operation. The implementation takes less than 30 lines of C#.

Recursive Merge Sort

public static T[] Recursive(T[] array, IComparer<T> comparer)
 {
     Recursive(array, 0, array.Length, comparer);
     return array;
 }
 
 private static void Recursive(T[] array, int start, int end, IComparer<T> comparer)
 {
     if (end - start <= 1) return;
     int middle = start + (end - start) / 2;
 
     Recursive(array, start, middle, comparer);
     Recursive(array, middle, end, comparer);
     Merge(array, start, middle, end, comparer);
 }

Iterative Merge Sort

public static T[] Iterative(T[] array, IComparer<T> comparer)
{
    for (int i = 1; i <= array.Length / 2 + 1; i *= 2)
    {
        for (int j = i; j < array.Length; j += 2 * i)
        {
            Merge(array, j - i, j, Math.Min(j + i, array.Length), comparer);
        }
    }
 
    return array;
}

Merge Function

The merge method below is used for both methods: recursive and iterative. It merges the two provided sub-arrays T[start, middle) and T[middle, end). The result of the merge cannot stored in the input array, it needs to be stored in a separate temporary array. This takes (end-start) memory space and will have a worst case space complexity O(n) where n is the size of the input array.

private static void Merge(T[] array, int start, int middle, int end, IComparer<T> comparer)
{
    T[] merge = new T[end-start];
    int l = 0, r = 0, i = 0;
    while (l < middle – start && r < end – middle)
    {
        merge[i++] = comparer.Compare(array[start + l], array[middle + r]) < 0
            ? array[start + l++]
            : array[middle + r++];
    }
 
    while (r < end – middle) merge[i++] = array[middle + r++];
 
    while (l < middle – start) merge[i++] = array[start + l++];
 
    Array.Copy(merge, 0, array, start, merge.Length);
}

Conclusion

As opposed to other in-place sorting algorithms, merge sort needs O(n) space to perform the merging step. On the other hand, it is a stable sort and it can be easily modified to implement external sorting for big data sets that do not fit in RAM.