CODEWITHSUNDEEP
algorithmsortingmerge
Celeritas
Celeritas

Reputation: 15083

What are the different types of merge sort used for?

I've been reading up on merge sort and so far I've seen three main different versions:

  1. abstract in-place (by the way, why is this called "in-place" when it's not?)
  2. top-down
  3. bottom-up

First, why are they all considered the same algorithm? Is it because the main idea is merging two sorted lists into one sorted list?

Second, when should which be used? The abstract in-place doesn't make recursive calls and I have heard claims that this is a good thing as it avoids deep call stacks (for example I've seen people go to great lengths implementing Quicksort without recursion). Does this mean abstract in-place uses the least memory?

TL;DR what's the difference between abstract in-place, top-down and bottom-up merge sort?

Upvotes: 5

Views: 4381

Answers (2)

T. Claverie
T. Claverie

Reputation: 12256

There is a slight misunderstanding here: Abstract in-place merge is not a mergesort, it is the routine used to merge two arrays together. The two flavors described by your link are bottom-up and top-down mergesort. They are exactly the same algorithm, whith the exact same compares and swap done. But the implementation relies on a different approach for each, this is where their name comes from.

Abstract in-place merge

The problem of merge sort is the extra space required to perform it. All of the schemes to make it in place are quite complicated and not very practical. This scheme is just an abstraction of what would a good in-place mergesort be like, and the implementation of this merge is easy. But it is not in-place, and still uses this extra O(n) memory.

Top-down mergesort

This is the most common one. It usually relies on recursivity, and uses top-down approach. That is : start with array of length n, and recursively sort the two halves, then merge them together. We call it top-down because we start by an array of length n and reduce the problem until we get an array of size 1.

Bottom-up mergesort

A second variant of mergesort, which works iteratively. As its name suggests, it uses a bottom-up approach. The intuition is straight-forward for this one: merge all subarrays of size 1, then merge all subarrays of size 2, then all of size 4, etc until the whole array is merged.

Performance

The two variants of mergesort have the same running time, because the operations are exactly the same. The difference lies in the implementation. One is iterative, the other is recursive. I guess people have their own preference about which is more understandable.

Concerning the size of the call stack, there is nothing to worry about. The call stack can not exceed log n for top-down mergesort, which is very little. It is good to avoid deep call stack, and such cases can occur on quicksort if the data is already sorted, but it will never happen with a mergesort.

Upvotes: 4

MBo
MBo

Reputation: 80287

Yes, all variants of mergesort use the same or similar merge phase.

There is no (AFAIK) real effective in-place merge sort, existing ones are very complicated and exhibit rather poor speed.

Top-down and bottom-up implementations are quite close, you can choose any. Recursion level is limited by log2(n), so deep stacks aren't possible

There are some more mergesort kinds - for example, natural mergesort is good for partially sorted data sets.

Upvotes: 2

Related Questions