Recursive Sorts:   Introduction

• The fastest sorting algorithms run in O(n.log(n))-time
  
  
• Under certain assumptions, i.e. a test can only compare two elements, e.g. a[ i ] <= a[ j ],   we cannot do better than n . log( n ), in general, because:
  
  
  1. There are n! permutations of n elements.
  2. Each comparison gives you (at most) 1-bit of information.
  3. Stirling's approximation:     log( n! ) ~ n . log( n ) + . . .
  4. So, need to gather about n.log(n) bits of information to discover the sorted permutation.
     
     
• Saw Heap Sort previously. Now, two more such fast sorts,   Merge Sort and Quick Sort . . .

How to solve a big problem?  Another Strategy:

• Divide it into two small sub-problems
  
  
• solve each sub-problem
  
  
• combine the results

Merge Sort( a [ ] )

• if length of a[ ] is "small"
  
  
  • sort a[ ] by some simple method
    
    
  • N.B. a single element is sorted
    
    
• else
  
  
  • part₁ = merge_sort 1st half of a[ ]
    
    
  • part₂ = merge_sort 2nd half of a[ ]
    
    
  • merge part₁ and part₂
end_if

Top-down Merge sort, e.g. merge_sort( a[ 1 .. 8 ] )

• copy a[ ] into b[ ]
  
  
• merge sort [ 1 .. 4 ]
  • merge sort [ 1 .. 2 ]
    • merge sort [ 1 .. 1 ] -- trivial
    • merge sort [ 2 .. 2 ] -- trivial
    • merge b[ 1 .. 1 ] and b[ 2 .. 2 ] into a[ 1 .. 2 ]
      
      
  • merge sort [ 3 .. 4 ]
    • merge sort [ 3 .. 3 ] -- trivial
    • merge sort [ 4 .. 4 ] -- trivial
    • merge b[ 1 .. 1 ] and b[ 2 .. 2 ] into a[ 1 .. 2 ]
      
      
  • merge a[ 1 .. 2 ] and a[ 3 .. 4 ] into b[ 1 .. 4 ]
    
    
• merge sort( [ 5 .. 8 ] )
  • . . . similarly . . .
    
    
• merge b[ 1 .. 4 ] and b[ 5 .. 8 ] into a[ 1 .. 8 ]

function mergeSort(int a[], int N)  /* wrapper routine */
/* NB sorts a[1..N] */

 { int i;
   int b[N];          /* -- the O(N) workspace */

   for(i=1; i <= N; i++)
      b[i]=a[i];      /* -- copy */

   merge(b, 1, N, a); /* -- does the real work . . . */
 }

function merge(int inA[], int lo, int hi, int opA[])
/* sort (input) inA[lo..hi] into (output) opA[lo..hi] */
 { int i, j, k, mid;

   if(hi > lo) /* at least 2 elements */
    { int mid = (lo+hi)/2;          /* lo <= mid < hi */
      merge(opA, lo,   mid, inA);   /*   sort the ... */
      merge(opA, mid+1, hi, inA);   /*    ... 2 halfs */

      i = lo;  j = mid+1;  k = lo;
      while( ... )                  /* and merge them */
       {
         ... merge the sorted inA[lo..mid] and inA[mid+1]
         ... into opA[lo..h]
       }/*while */
    }/*if  */
 }/*merge */

time complexity

1. merging n elements takes O(n)-time
2. there are log₂(n) levels of recursion   [lecturer: draw picture]
3. n elements are merged at each level
4. therefore O( n . log(n) )-time in total, always

space complexity

• O(n)-space, for the extra "work-space" array

Stability

• merge sort is stable (with care)

There is also a bottom-up merge sort,   e.g. merge sort a[ 1 .. 8 ]

• copy a[ ] into b[ ]
  
  
• section_length := 1
  • merge b[ 1 .. 1] and b[ 2 .. 2 ] into a[ 1 .. 2]
  • merge b[ 3 .. 3] and b[ 4 .. 4 ] into a[ 3 .. 4]
  • merge b[ 5 .. 5] and b[ 6 .. 6 ] into a[ 5 .. 6]
  • merge b[ 7 .. 6] and b[ 8 .. 8 ] into a[ 7 .. 8]
    
    
• section_length := 2
  • merge a[ 1 .. 2] and a[ 3 .. 4 ] into b[ 1 .. 4]
  • merge a[ 5 .. 6] and b[ 7 .. 8 ] into a[ 5 .. 8]
    
    
• section_length := 4
  • merge b[ 1 .. 4] and b[ 5 .. 8 ] into a[ 1 .. 8]

By the way:

• In-situ merging is possible in
  
  
  • O(1) extra space and
    
    
  • O(n)-time
    
    
• The algorithm is "difficult", beyond this subject(!), (?challenge?)
  
  
• See the bibliography for references, if interested.

Quick Sort

1. move all the "small" elements to the left hand and move all the "large" elements to the right hand
   
   
2. sort the small elements
   
   
3. sort the large elements
   
   

Beware

• simple idea
• many ways to program, but
• many ways to get it wrong!   Been there, done that.

Partitioning:   Dutch National Flag (DNF) problem

• the partition operation is central to quick sort
  
  
• related to the [Dutch National Flag] problem - Dijkstra
  
  
  • 2-colour flag - optional
  • 3-colour flag   [lecturer explain: you will need to take notes]

Properties of DNF (only):

• O(n)-time complexity
  
  
• O(1)-space complexity
  
  
• not stable,   because [___________________]

Dutch National Flag related to Quick Sort

• 3-colour flag
  
  
  • red - smaller than median
    
    
  • white - equal to median
    
    
  • blue - greater than median

quicksort(int a[], int lo, int hi)   /* sort a[lo..hi] */
 { int left, right, median, temp;

   if( hi > lo ) /* i.e. at least 2 elements, then */
    { left=lo; right=hi;
      median=a[lo];  /* NB. just an estimate! */

      while(right >= left) /* partition a[lo..hi] */
      /*INV: a[lo..left-1] <= median & a[right+1..hi] >= median */
       { while(a[left]  < median) left++;

         while(a[right] > median) right--;

         if(left > right) break;

         temp=a[left]; a[left]=a[right]; a[right]=temp; /* swap */
         left++; right--
       }
      /* a[lo..left-1] <= median and a[right+1..hi] >= median
         and left > right */

      quicksort(a, lo, right); /* divide and */
      quicksort(a, left,  hi); /* conquer */
    }
 }/*quicksort*/

Properties of Quick Sort

• Time Complexity
  
  
  • O(n²)-time, worst case
    
    
  • O(n . log(n))-time, on average
    
    
• Space Complexity
  
  
  • O(log(n))-space, provided: we remove the recursion (i.e. use an explicit stack), & sort the smaller partition first (i.e. stack the larger one)
    
    
  • because [______________]
    
    
• not stable

Recursive Sorting Summary

• cannot in general do better than O( n . log(n) )-time
  
  
• but, e.g. O(n)-time possible if elements are bounded.
  
  
• Quick sort is quickest almost always,   but has a bad worst-case
  
  
• Heap sort and merge sort guaranteed O( n . log(n) )-time, always

Prepare

• dynamic programming paradigm,   e.g. edit distance