Platinum Partner
java,python,javascript,c-sharp,algorithm

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.

Published at DZone with permission of {{ articles[0].authors[0].realName }}, DZone MVB. (source)

Opinions expressed by DZone contributors are their own.

{{ tag }}, {{tag}},

{{ parent.tldr }}

{{ parent.urlSource.name }}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet