Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
