Analysis of Merge Sort Algorithm

no_mkd

I. Pros and Cons of Merge Sort

There should be a reason to spend effort understanding it:

• Merge sort efficiency reaches its peak: time complexity is O(nlogn), which is the highest level achievable by comparison-based sorting algorithms
• Merge sort is a stable algorithm (i.e., elements with equal values maintain their pre-sort order during sorting; for example, ascending sort result of 3212 is 1223, the order of the two 2s remains unchanged before and after sorting), which is crucial in certain scenarios
• Merge sort is the most commonly used external sorting method (when records to be sorted are stored on external storage and memory cannot hold all data, merge sort still applies; of course, merge sort is also suitable for internal sorting...)

Disadvantages:

• Merge sort requires O(n) auxiliary space, while quicksort and heapsort with similar efficiency require O(logn) and O(1) auxiliary space respectively; among similar algorithms, merge sort's space complexity is slightly higher

P.S. This article only discusses the most original "two-way merge"; multi-way merges are similar

II. Internal Principles

First, we need to know that the principle of merge sort is: divide and conquer, the same as quicksort

Algorithm principle: unordered -> partially ordered -> fully ordered

The "divide" and "conquer" processes in merge sort are combined together, meaning each pass does both "divide" and "conquer" work, not "divide" completely first then "conquer" ("divide" is simple, just keep halving until it can't be divided further, right? Wrong, if you divide completely you won't be able to merge back together. Remember, "divide" and "conquer" are combined together)

One diagram is enough to explain the merge sort process:

Explanation: Compare P1 with P2, place the larger (smaller) one into P, then move P1 or P2 right (move whichever was placed), finally move P right

For example, to sort array a[n] in ascending order, the specific process is as follows:

1. Apply for two auxiliary spaces each of length n/2, put array a into them, first half into L, second half into R
2. Perform one round of comparisons according to the explanation above (P moves from A to C, one pass ends)

Now think about what we achieved after one pass of sorting:

1. Achieved partial ordering (first half < second half, right?)
2. Besides that, we naturally split the sequence to be sorted into two halves, preparing for recursion

Still not clear enough? Here are a few more statements:

1. The diagram explains why auxiliary space of length n is needed
2. As long as L and R are each internally ordered (both ascending or both descending), then only one more merge pass is needed to complete the sort (think about it carefully, isn't that right?)
3. The sorting part is the merging part (remember the statement mentioned above? The "divide" and "conquer" processes are combined together, never think of them separately, otherwise you'll find they can't be merged back together...)

III. Implementation Details

If the explanation above is still not clear enough, let's work through an example step by step:

Assume the sequence to be sorted is a[] = {3, 2, 1, 4}, then the specific process is as follows:

P.S. What if the sequence to be sorted has an odd number of elements? Is this a problem? It just means the first half has one less element than the second half; single-pass loop control is done by the P pointer, so there's no issue of some P1 not having a paired P2 to compare with

IV. Summary

Merge sort is mostly used in scenarios requiring external sorting; besides that, merge sort is also used when internal sorting needs to guarantee stability (internal sorting not requiring stability generally uses quicksort or heapsort; the former has low efficiency when the sequence to be sorted is basically ordered, the latter has issues with heap maintenance)