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.