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.
$20$ $47$ $15$ $8$ $9$ $4$ $40$ $30$ $12$ $17$ \ / \ / \ / \ / \ / $20$ $47$ $8$ $15$ $4$ $9$ $30$ $40$ $12$ $17$ after $1$st pass \ / \ / \ / \ / \ / \ / $8,15,20,47$ $4,9, 30,40$ $12,17$ after $2$nd pass
Answer is B.
sir, not seen the solution to this particular question but, asking if this is possible for this question. http://www.geeksforgeeks.org/merge-sort/ - here they are using top-down approach (see the numbering of operations -depth first left first, very different from here used in answer) https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation - Wikipedia
@ Vikrant Singh
can any one clarify what a pass exactly means?
because if pass means function exe then i think it would be different what is stated here.
Because as far as i know only first half portion of array is altered , not the entire array.
correct me if I am wrong
@ Rupendra Choudhary I too think Divide and Conquer algorithms should work in a top-down way by default. I mean shouldn't you first divide the lists before you start merging them if you call Merge-Sort Divide and Conquer? Perhaps the term "elements" implies that our input was not a single list but separate sorted ones? Maybe the word "straight" is supposed to mean you directly start merging the elements into sorted lists? At this point this seems more of an English question than an Algorithms one.
If this question is really asking for Straight 2 way merge sort, this is the procedure given by Knuth. But none of the answers is matching by following this method.
https://books.google.co.in/books?id=RlQqhEcLruUC&pg=PA162&lpg=PA162&dq=straight+two-way+merge+sort&source=bl&ots=dunjtRPWBX&sig=_DBjxmAT2Eb-dz9kWEJHejgeUyE&hl=en&sa=X&ved=2ahUKEwi_4_HhgKDfAhXPV30KHZA8Aq44ChDoATADegQIBxAB#v=onepage&q=straight%20two-way%20merge%20sort&f=false
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