0
$\begingroup$

I understand how the divide part of the algorithm works and how it is meant to spread efforts.

What I don't understand is how would you merge blocks [7][14] and [3][12] or [9][11] and [2][6]. For the latter part it's easy enough as you just concatenate them ( although how do you know that? ) but for [7][14] and [3][12] you have to rearrange their indexes for the order to be increasing. How in software/pseudocode do you implement that step?

pic

$\endgroup$
  • 2
    $\begingroup$ The answer to this question is contained in any reasonable description of mergesort. Which descriptions did you look at? What didn't you understand about them? Even without somebody else's description, can you not think of any way to merge two sorted lists into a single sorted list? $\endgroup$ – David Richerby Nov 24 '15 at 12:06
  • $\begingroup$ Only think I can think of is iterating through each sub array simultaneously and comparing the elements. $\endgroup$ – mega_creamery Nov 24 '15 at 12:10
  • 3
    $\begingroup$ And that's exactly correct. $\endgroup$ – David Richerby Nov 24 '15 at 12:32
4
$\begingroup$

The merge subroutine takes two sorted arrays and creates one sorted array out of these two arrays. It does so in linear time.

Say the sorted arrays are A = [1 2 3] and B = [2 3 4]. Since these two are already sorted, the minimum is going to be either the first element in A or the first element in B. So take the minimum among these two values and append it to the output array C. We get C = [1] and the two arrays now look like A = [2 3] and B = [2 3 4] (you don't have to remove 1 from A, you can increment an index to implement this step).

Now iterate this process until both arrays are empty and the final sorted array is C.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.