If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:
$20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$
then the order of these elements after second pass of the algorithm is:
$8, \ 9, \ 15, \ 20, \ 47, \ 4, \ 12, \ 17, \ 30, \ 40$
$8, \ 15, \ 20, \ 47, \ 4, \ 9, \ 30, \ 40, \ 12, \ 17$
$15, \ 20, \ 47, \ 4, \ 8, \ 9, \ 12, \ 30, \ 40, \ 17$
$4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$
Hi Guys,
Notice the word Two-Way merge sort. It could be N-ways also.
https://stackoverflow.com/questions/56696667/2-way-merge-sort-and-merge-sort
General tip:
The n-way merge sort is the iterative version and the usual merge sort is the recursive version.
I got easily confused with the two versions of merge sort in the beginning.
An example to understand the difference between $2$ – way MergeSort (Iterative version) and MergeSort (Recursive version) has been explained by satbir in the below question.
https://gateoverflow.in/89083/gate1989-9
The answer is B.
I am not sure what the pass means here. if it means merging.. then shouldn't the answer be 15,20,47,8,9,4,40,30,12,17.
As per my understanding, first the mergesort algorithm will keep splitting the array recursively and continue further by taking the left part. i will then start merge from bottom up, including the right parts as it goes up. So first all of the left array would br sorted followed by the right part and finally the last pass of merging.
We can draw recursion tree in 2 ways:
1) By being biased on the right sub-array during partition with odd number of elements. This would give 20,47,15,8,9,4,40,30,12,17 after 2 calls to merge function.
2) By being biased on the left sub-array during partition with odd number of elements. This would give 15,20,47,8,9,4,40,30,12,17 after 2 calls to merge function.
I think in the question they are talking about iterative mergesort. Reference: https://www.geeksforgeeks.org/iterative-merge-sort/
// Merge subarrays in bottom up manner. First merge subarrays of // size 1 to create sorted subarrays of size 2, then merge subarrays // of size 2 to create sorted subarrays of size 4, and so on. for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size) { // Pick starting point of different subarrays of current size for (left_start=0; left_start<n-1; left_start += 2*curr_size) { // Find ending point of left subarray. mid+1 is starting // point of right int mid = min(left_start + curr_size - 1, n-1); int right_end = min(left_start + 2*curr_size - 1, n-1); // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end] merge(arr, left_start, mid, right_end); } }
By 2 passes they mean to say 2 iterations of the outer for loop in the above code.
First iteration of the outer for loop would merge all 1-sized array elements.
Second iteration of the outer for loop would merge all 2-sized array elements.
Here they are asking about the result after 2nd pass, since pass will not give a useful meaning in recursive top-down approach, we have to use bottom-up approach (also because qns mentions "2-way merge", 2-way merge actually works in bottom-up manner). To know the working of bottom up approach and difference between top-down and bottom up approach of merge sort: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/merge-sort5.html https://stackoverflow.com/questions/17417887/where-is-bottom-up-merge-sort-useful
Two Way MergeSort is Different from Merge Sort
Two way MergeSort is Iterative Procedure while MergeSort is Recursive Procedure
Maybe this video help understanding 2-way(or M-way) merging better...
https://www.youtube.com/watch?v=6pV2IF0fgKY
64.3k questions
77.9k answers
244k comments
80.0k users