2-way Merge Sort and Merge Sort

Admin 1
Viewed 14079

How 2-way Merge Sort are different from Merge Sort recursively?

Suppose there are 5 number to be sorted 8,9,1,6,4 In Merge Sort we divide like this Step1: {8,9,1} {6,4}

Step2: {8,9} {1} {6} {4}

Step3:{8} {9} {1} {6} {4}

Now Merge

Step4: {8,9} {1} {4,6}

Step5: {1,8,9} {4,6}

Step6: {1,4,6,8,9}

But in 2 way merge sort, we divide the array in 2 elements each(but according to wikipedia , before merging every 2 element parts need to be sorted.https://en.wikipedia.org/wiki/K-way_merge_algorithm )So, it also starts from single element and merge them right? So, steps for array :8,9,1,6,4

Step1:{8,9} {1,6} {4} [that is odd element merge at last]

Step2: {1,6,8,9}. {4}

Step3: {1,4,6,8,9}

So, number of steps reduces here. Then what will be algorithm for it? Is 2-way merge sort merge sort more efficient than merge sort?

mergesort algorithm
1 Answers

Is 2-way merge sort merge sort more efficient than merge sort?

Another name for an iterative 2-way merge sort is bottom up merge sort, while another name for recursive merge sort is top down merge sort.

Generally, an optimized bottom up merge sort is slightly more efficient than an optimized top down merge sort. Top down merge sort performs O(n) stack operations on indexes generated by the recursive "splitting" of the array. If n is not a power of 2, then bottom up merge sort does more compare and moves, but it's less than top down merge sort's stack operation overhead. For large arrays, the difference is less than 5%.

For a hybrid insertion / merge sort, that uses insertion sort on n / m groups of m elements, bottom up merge sort can adjust m to deal with n not being a power of 2.

Top down merge sort is mostly for learning. Despite the small difference in performance and stack space, most libraries use some variation of bottom up merge sort for a stable sort.

user_32820560
Related