CmSc 250 Intro to Algorithms


Sorting Algorithms
MergeSort

  1. MergeSort Algorithm
  2. Example of MergeSort
  3. Analysis of MergeSort

Animation

Learning Goals
Exam-like questions


  1. Mergesort

    • Recursive algorithm.
    • Runs in O(NlogN) time.

    Basic idea: If we have two sorted arrays, we can merge them in linear time
    with N comparisons only. Given an array to be sorted, we can consider separately
    its left half and its right half, sort them and then merge them.

    Where is the recursion?

    Each half is an array that can be sorted using the same algorithm -
    divide into two, sort separately the left and the right halves, and then merge them.

  2. Example

    1. Merging two sorted arrays:
    2. Array A: 3, 7, 10, 15
      Array B: 1, 4, 8, 9, 20
      Array C: (merged)

      1, 3, 4, 7, 8, 9, 10, 15, 20

    3. Mergesorting an array:

    6, 9, 1, 10, 34, 12, 15, 8

    The following figure gives the state of the array at each step of the mergesort algorithm.
    Each splitting is indicated in blue, each merging - in purple.
    Parts merged at some previous step are in gray.

  3. Analysis of MergeSort Algorithm

  4. Algorithm:

    
    mergesort( int [] a, int left, int right)
    {
    	if (right > left)
    	{
    		middle = left + (right - left)/2;
    		mergesort(a, left, middle);
    		mergesort(a, middle+1, right);
    		merge(a, left, middle, right);
    	}
    }	
    

    Assumption: N is a power of two.

    For N = 1: time is a constant (denoted by 1)

    Otherwise: time to mergesort N elements = time to mergesort N/2 elements plus
    time to merge two arrays each N/2 elements.

    Time to merge two arrays each N/2 elements is linear, i.e. N

    Thus we have:

    (1) T(1) = 1

    (2) T(N) = 2T(N/2) + N

    Next we will solve this recurrence relation. First we divide (2) by N:

    (3) T(N) / N = T(N/2) / (N/2) + 1

    N is a power of two, so we can write

    (4) T(N/2) / (N/2) = T(N/4) / (N/4) +1

    (5) T(N/4) / (N/4) = T(N/8) / (N/8) +1

    (6) T(N/8) / (N/8) = T(N/16) / (N/16) +1

    (7)
    (8) T(2) / 2 = T(1) / 1 + 1

    Now we add equations (3) through (8) : the sum of their left-hand sides
    will be equal to the sum of their right-hand sides:

    T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + + T(2)/2 =

    T(N/2) / (N/2) + T(N/4) / (N/4) + .+ T(2) / 2 + T(1) / 1 + LogN

    (LogN is the sum of 1s in the right-hand sides)

    After crossing the equal term, we get

    (9) T(N)/N = T(1)/1 + LogN

    T(1) is 1, hence we obtain

    (10) T(N) = N + NlogN = O(NlogN)

    Hence the complexity of the MergeSort algorithm is O(NlogN).


Learning Goals

  • Be able to explain how mergesort works and what its complexity is.

Exam-like questions

  1. Show that the complexity of mergesort algorithm is O(NlogN) by using recurrence relations
  2. Given an array e.g. 17, 23, 10, 1, 7, 16, 9, 20, sort it on paper using mergesort
    Write down explicitly each step.

Back to Contents page
Created by Lydia Sinapova