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.

Pingback: Tweets that mention A Recursive and Iterative Merge Sort Implementations - Chaker Nakhli's Blog -- Topsy.com

## Thomas Mueller

March 7, 2012 at 8:13 pmMerge sort can be implemented in-place and stable, even thought it is a bit complicated. An implementation is included in the C++ STL. There is a link to a Java implementation at http://en.wikipedia.org/wiki/Merge_sort#cite_note-3

Pingback: Sort LinkedList in O(nlogn) time using constant space complexity | akajj