3
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

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). $$

$\endgroup$
1
  • $\begingroup$ Nice worst-case example. Starting with a completely sorted list, you only need to move seven numbers out of place, and most of them don't need to move very far. $\endgroup$
    – David K
    May 7 at 20:47
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.