Sorting Technique - Merge Sort

Q.1) What is the process of merge sort?

Merge sort takes two unsorted subarray and combine them into single sorted array.

Q.2) What is the advantage of merge sort?

Merge sort is faster in sorting elements as it avoids Swapping (interchanges).

It does not require all elements in memory, hence it is best suitable for virtual memory environment. (refer to quick sort for more on virtual memory)

Q.3) What is an efficiency of merge sort?

Merge sort requires O(nlogn) comparisons irrespective of order of elements. It has worst case. On the other hand, it requires O(2n) space, as it merging process needs another temporary array to hold merged elements in every pass.

Please note, logn(Log n to the base 2) are the passes in merge sort.

Q.4) What are the limitations of merge sort?

It requires twice additional space and it has too many assignment operations.

Q.5) Write a non-recursive function to implement merge sort.

#include <stdio.h>

#define MAXSZ 10

void mergesort(int a[], int n)

{

    int aux[MAXSZ];

    int i,j,k,l1,l2,size,u1,u2;

    size = 1;

    while (size < n)

    {

        l1 = 0;

        k = 0;

        while (l1+size < n)

        {

            l2 = l1+size;

            u1 = l2-1;

            u2 = (l2+size-1 < n) ? l2+size-1 : n-1;

            for(i = l1, j = l2; i<= u1 && j <= u2; k++)

                if (a[i] <= a[j])

                    aux[k] = a[i++];

                else

                    aux[k] = a[j++];

            for(; i <= u1; k++)

                        aux[k] = a[i++];

            for(; j <= u2; k++)

                        aux[k] = a[j++];

            l1 = u2+1;

        }

        for (i=l1;k<n;i++)

                aux[k++] = a[i];

        for(i=0; i<n; i++)

                a[i] = aux[i];

        size *= 2;

    }

}

Q.6) Compare and contrast Quick Sort and Merge Sort.

i) Quick sort sorts single element (called pivot) and partitions array into two sub - arrays. The process continues till we finally get n sub-arrays of size 1. Merge sort on the other hand starts with n sub-arrays of size 1 and merge them till we get single array of size n. (Exactly opposite process).

ii) Quick sort can be either implemented using recursion or by using stack; pure iterative version of quick sort is not possible. However, merge sort can be implement using recursion , stack as well as using iterative version. (See Q.5)

iii) Time complexity of Quick Sort is O(nlogn) which is in best case when elements are not sorted at all. But, if elements are sorted or oppositely sorted, quick sort performs poorly with time complexity O(n-square). Merge sort does not have any worst case, it has time complexity O(nlogn), irrespective of order of elements.

iv) Quick sort is an partition exchange sort which requires two critical operations - comparison and swapping. Merge sort has only comparisons, no swapping but does too many assignment operations. In general, merge sort is faster than quicksort.

v) Space complexity of quick sort is O(n+1) - it needs one additional memory location for swapping. Merge sort takes twice space, resulting into space complexity of O(2n). Merge sort requires double space as in merging process , it has to copy elements temporarily into another array.

Want to read more?

Subscribe to questionbankos.com to keep reading this exclusive post.

Subscribe Now