*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.

## Comments

## Goel Yatendra replied on Thu, 2012/03/15 - 1:44pm