Next, we're going to look at a bottom-up version of Mergesort. Well, Mergesort is
easy to understand as a recursive program. This bottom-up version that has no
recursion, it's also quite simple to understand and to code up. The basic idea
is to think of the array as being a little at the begining a set of little sorted sub
arrays of size one. And then what this method will do is go through and merge
those little subarrays of size one together in pairs to get subarrays of size
two. Then, the whole array consists of sorted subarrays to size two, and
then we make another pass through to get size four, and then size eight, and so
forth. So, as you can see in this example we start out by merging the first two sub
arrays of size one to make a array of size two - E, M - that's sorted, and then do the same
thing for the next two elements and the next two and so forth until eventually
instead of sixteen individual elements we have eight sorted subarrays of size two.
Then on another pass through, we can take the E, M and the G, R and merge them
together to make EGMR, and the E, S and the O, R merge those together to make EORS, and
so forth. And we have four subarrays of size four. One more pass makes two
subarrays of size eight, and the last pass is just a sorted array. The bottom line in
this is sequence of passes through the whole array and there's no recursion
needed at all. It's extremely easy to code up as you can see from this code. We use
the same merge code as before and we take a nested for loop. The first one is the
size of the subarray and this loop gets executed on a log N times because each time
we double the size of the subarray until we get to N. And then we pass through
picking out from low to low+size-1, and then the next part is low+size+size-1
until we run to the end of the array where we might not have a full
subarray of size sz. That is a fully complete industrial strength code for
sorting. The only downsize as would regular Mergesort is that it uses extra
space proportional to the size of the array. But otherwise, that's a fine method
for merging. That's a bottom-up Mergesort. If you look at this visual trace you can
see how it works. The thing is totally unsorted, then it gets sorted until
subarrays to size four, then eight, sixteen, and 32. Now in this case the
second subarray to be sorted is smaller but the merge routine doesn't really care
about that so much. You can merge things that are not equal in size. And then we get
a final sorted array. Whatever the size, bottom of Mergesort gets the job done in
log N passes. Each pass using about N compares for a total cost of about N log N.