2
$\begingroup$

Below is the solution to a merge sort exercise - "Use a merge sort to sort the list". I'm confused because I thought that there needed to be an initial phase of breaking the list in to sub-lists, yet here only the "reconstruction" phase is shown.

Am I missing something, or is there a problem with the given solution please?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ It appears that the first step does indeed break the list into sublists: each with one element. $\endgroup$ – Rick Decker Aug 16 at 14:50
3
$\begingroup$

What is pictured is often called "bottom up mergesort", which is contrast to the "normal" mergesort, which you could call "top down merge sort".

You can find them contrasted in this article from Algorithms:

Bottom-up mergesort. Even though we are thinking in terms of merging together two large subarrays, the fact is that most merges are merging together tiny subarrays. Another way to implement mergesort is to organize the merges so that we do all the merges of tiny arrays on one pass, then do a second pass to merge those arrays in pairs, and so forth, continuing until we do a merge that encompasses the whole array. This method requires even less code than the standard recursive implementation. We start by doing a pass of 1-by-1 merges (considering individual items as subarrays of size 1), then a pass of 2-by-2 merges (merge subarrays of size 2 to make subarrays of size 4), then 4-by-4 merges, and so forth.

We don't need to use recursive calls to decide how to break down the array. Rather, it's implicit which elements can be grouped with which elements by simply grouping them into powers of two. This version of merge sort can be more easily written without recursion, which removes some overhead. It's also seems more amenable to various optimizations, such as SIMD or other vectorized operations, loop unrolling, etc.

$\endgroup$
2
$\begingroup$

Presumably the diagram only shows the steps of merge-sort beyond the point where the sub-array to be sorted contains only one element, i.e. as you rightly said, the reconstruction phase.

enter image description here

In other words, your diagram may have skipped the first three levels of the procedure as shown above. Note that these levels can be reconstructed from the reconstruction phase, hence they may be dropped entirely.

I wouldn't say there is a problem in the solution, not one unintended at least. At the outset, it seems it is a niche notation the author of a book might have adopted for the sake of brevity.

$\endgroup$
  • 1
    $\begingroup$ What seems odd to me is that if we break the original list into sub-lists by "cutting in half", then there will be some 3, 2 length pairs which do not appear in the solution - it seems to lack symmetry and I can't see how it relates to the merge sort algorithm as I have seen it. $\endgroup$ – Robin Aug 17 at 12:36
  • $\begingroup$ @Robin The triplets/pairs are further broken down, if I remember correctly, until the array to be sorted consists of only one element, beyond which no recursive function calls happen. I have edited my answer to include an example, and indicated where your diagram intends to pick up the merge sort procedure. $\endgroup$ – Shubham Johri Aug 17 at 12:45
  • $\begingroup$ OK, but in your answer there is vertical symmetry about the middle row. In mine, the steps don't seem to correspond to how the initial list would be divided - can you see what I mean? $\endgroup$ – Robin Aug 17 at 12:51
  • $\begingroup$ @Robin Yes, that is what I'm trying to address. You can recreate those 'division' steps with what you've been given, which is why they could have been omitted altogether. For example, in your diagram, the second last row suggests that the array was originally divided into two subarrays, the first containing the first eight elements and the other with the last two elements. The first subarray then got subsequently divided into half, so did the second, until only one element was left. So you can reverse engineer the division by the reconstruction, which might have been why the former was dropped $\endgroup$ – Shubham Johri Aug 17 at 13:17

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.