Merge sort seems to take the same number of comparisons for best and worst case.

Question

I am trying to clear up my conceptions of merge sort. What I cannot understand how merge sort takes less number of comparisons during best case.

Let me explain, looking at the merge procedure given below, I can make some inferences. First, merge sort will always take $\log_2{n}$ divisions. Whether it is best or the worst case. The depth of the tree will always be the same. Second, the number of comparisons should always be the same, since the $if$ (comparison) block is always used.

void merge(int arr[], int l, int m, int r) 
{ 
    // Find sizes of two subarrays to be merged 
    int n1 = m - l + 1; 
    int n2 = r - m; 

    /* Create temp arrays */
    int L[] = new int [n1]; 
    int R[] = new int [n2]; 

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i) 
        L[i] = arr[l + i]; 
    for (int j=0; j<n2; ++j) 
        R[j] = arr[m + 1+ j]; 


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays 
    int i = 0, j = 0; 

    // Initial index of merged subarry array 
    int k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 

    /* Copy remaining elements of L[] if any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 

    /* Copy remaining elements of R[] if any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 

What I can't understand is why people say that the number of comparisons will be less for the best case and more for the worst case. Looking at the algorithm I just don't see how that is possible.

Lets take to lists:

$L_1 = \{a_1,a_2,a_3,a_4\}$

$L_2 = \{b_1,b_2,b_3,b_4\}$

Regardless of the fact that whether all elements of $L_1$ is less than $L_2$ (best case) or all elements of $L_1$ are greater than $L_2$ (worst case), the merge procedure will use the exact same number of operations to determine how to merge the lists.

Then why the difference in the number of comparisons between the best and worst case?

Answer 1

When merging $L_1 = (a_1, a_2, a_3, a_4)$ and $L_2 = (b_1, b_2, b_3, b_4)$, it's true that we need $4$ comparisons when all elements of $L_1$ come before all elements of $L_2$ (which is the best case). It's also true that we need $4$ comparisons when all elements of $L_2$ come before all elements of $L1$.

But this is not the worst case: one possible worst case is $a_1 < b_1 < a_2 < b_2 < a_3 < b_3 < a_4 < b_4$, in which the elements of $L_1$ and $L_2$ are interleaved. Here, we will:

1. Compare $a_1$ to $b_1$, and put $a_1$ in the merged list.
2. Compare $a_2$ to $b_1$, and put $b_1$ in the merged list.
3. Compare $a_2$ to $b_2$, and put $a_2$ in the merged list.
4. Compare $a_3$ to $b_2$, and put $b_2$ in the merged list.
5. Compare $a_3$ to $b_3$, and put $a_3$ in the merged list.
6. Compare $a_4$ to $b_3$, and put $b_3$ in the merged list.
7. Compare $a_4$ to $b_4$, and put $a_4$ in the merged list.

Then, after the $7^{\text{th}}$ comparison, we may put $b_4$ (the remaining element of $L_2$) in the merged list. So the worst case is in fact worse than the best case.

In general:

• Merging $L_1$ and $L_2$ will take $\min\{|L_1|, |L_2|\}$ comparisons in the best case, when all elements of the shorter array come before all elements of the longer list. (Of course, the two lists are often the same size, but sometimes one is shorter by one element.)
• Merging $L_1$ and $L_2$ will take $|L_1|+|L_2|-1$ comparisons in the worst case, when we have to compare their last elements. This happens when the lists are interleaved, but more generally any time the last and next-to-last element of the merged list started in different halves (one in $L_1$, the other in $L_2$).

In the simple case $n=2^k$, the best-case scenario requires $k 2^{k-1}$ comparisons. (There are $k$ levels of merge operations; at the $i^{\text{th}}$ level from the top there are $2^{i-1}$ merge operations which take $2^{k-i}$ comparisons each, for $2^{k-1}$ total.)

For the same $n$, the worst-case scenario requires $k 2^k - 2^k + 1$: nearly twice as many. (There are $k$ levels of merge operations; at the $i^{\text{th}}$ level from the top there are $2^{i-1}$ merge operations which take $2^{k-i+1}-1$ comparisons each, for $2^k - 2^{i-1}$ total.)

For each of these, it should really be checked that we can actually find an input (a list in some order) such that at every merge step, we see the best/worst case respectively. To achieve the best case, just start with an input that's already sorted. We can construct a worst case recursively. Given a set of $2^k$ inputs we must order somehow, divide it into two equal parts such that the last and next-to-last element are in different parts. Order each part according to the worst case for $2^{k-1}$ inputs, and put one part after the other.

Notably, this worst-case input may still look nearly sorted (to your eye, but not to merge sort's), For example, here is one possible worst-case input of length $16$: $$ (1, 3, 2, 7, 4, 6, 5, 15, 8, 10, 9, 14, 11, 13, 12, 16). $$

Answer 2

I know this question is old, but I found the answers above this cover the concepts, but I found none hit the core question asked...how does best-case actually save comparisons. I found working it out on paper/visually was the only thing that made sense.

The critical difference is that in our best-case, the ordering of values allows us to verify that all values in the left (or right) subarray are less than the remaining values in the right subarray. Thus, shaving off comparisons. See the examples below.

Worst-Case (interleaved):

Original Array: $[0,4,2,6,1,5,3,7]$

First Partition: $[0,4,2,6]$ $[1,5,3,7]$

Second Partition: $[0,4]$ $[2,6]$ $[1,5]$ $[3,7]$

Third Partition: $[0]$ $[4]$ $[2]$ $[6]$ $[1]$ $[5]$ $[3]$ $[7]$

First Round of comparisons: 4 comparisons

$[0]<[4]$, $[2]<[6]$, $[1]<[5]$, $[3]<[7]$ (4 comparisons)

$[0,4]$ $[2,6]$ $[1,5]$ $[3,7]$

Second Round Comparisons: 6 comparisons

$[0]<[2]$, $[4]>[2]$, $[4]<[6]$ (3 comparisons, 6 is largest append w/o compare)

$[1]<[3]$, $[5]>[3]$, $[5]<[7]$ (3 comparisons, 7 is largest append w/o compare)

$[0,2,4,6]$ $[1,3,5,7]$

Third Round comparisons: 7 comparisons

$[0]<[1]$, $[2]>[1]$, $[2]<[3]$, $[4]>[3]$, $[4]<[5]$, $[6]>[5]$, $[6]<[7]$ (7 comparisons, 7 is largest append w/o compare)

$[0,1,2,3,4,5,6,7]$

Best-Case (all left < all right):

Original Array: $[0,1,2,3,4,5,6,7]$

First Partition: $[0,1,2,3]$ $[4,5,6,7]$

Second Partition: $[0,1]$ $[2,3]$ $[4,5]$ $[6,7]$

Third Partition: $[0]$ $[1]$ $[2]$ $[3]$ $[4]$ $[5]$ $[6]$ $[7]$

First Round of comparisons: 4 comparisons

$[0]<[1]$, $[2]<[3]$, $[4]<[5]$, $[6]<[7]$ (4 comparisons)

$[0,1]$ $[2,3]$ $[4,5]$ $[6,7]$

Second Round Comparisons: 4 comparisons

$[0]<[2]$, $[1]<[2]$ (2 comparisons, 2 & 3 are largest append w/o compare)

$[4]<[6]$, $[5]<[6]$ (2 comparisons, 6 & 7 are largest append w/o compare)

$[0,1,2,3]$ $[4,5,6,7]$

Third Round comparisons: 4 comparisons

$[0]<[4]$, $[1]<[4]$, $[2]<[4]$, $[3]<[4]$ (4 comparisons, entire right array is largest append w/o compare)

$[0,1,2,3,4,5,6,7]$

Answer 3

The advantage of merge sort in best cases arises when you sort linked lists. For example if you merge one list L1 with another L2 whose elements are all smaller, you will scan L1 and then directly attache L2 at the end of L1. That makes for $O(n_1)$ operations as opposed to $O(n_1+n_2)$.

If you want to work on arrays there are better options than merge sort.

Answer 4

The default Mergesort uses the default Merge algorithm, so we have to look at this to understand why it is better in best case.

• In best case, the default merge algorithm requires only $m$ comparisons for merging two sorted sequences of sizes $m$ and $n$.
• In average case, the default merge algorithm requires $m+n - ((m/(n+1)) + (n/(m+1)))$ comparisons for merging two sorted sequences of sizes $m$ and $n$.
• In worst case, the default merge algorithm requires $m+n-1$ comparisons for merging two sorted sequences of sizes $m$ and $n$.

Additionally, in best case the runtime of the algorithm will be much faster because the CPU branch predictor will have nearly 100% accuracy in this case.

So, in best case with the default Mergesort we will only have improvements that come from the Merge routine.

When people say, Mergesort is much faster in best case, they often mean a Natural Mergesort variant like Powersort or Timsort. Those algorithms scan the input in a first step for already sorted parts (called runs). And then they merge these already sorted runs. Because of this, Natural Mergesorts are highly adapative and much faster in best case for data that is already sorted or nearly sorted.

But we can also get the default Mergesort to be very adaptive. But we would need to replace the merging routine here. The default merging routine is not adaptive and requires a Natural Mergesort for the adaptiveness. If we don't use a natural Mergesort, the merge routine becomes adpative by using a binary search. In worst case that will bring us $\approx 1.5$ times extra comparisons. This is the case, when the data is not sorted or completely random.