[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:45:43 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

## 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
- divide and conquer problem solving strategy or paradigm- Alexander the Great.

## Merge Sort( a [ ] )

• if length of a[ ] is "small"

• sort a[ ] by some simple method

• N.B. a single element is sorted

• else

• part1 = merge_sort 1st half of a[ ]

• part2 = merge_sort 2nd half of a[ ]

• merge part1 and part2
• 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 ]
[lecturer: briefly or can skip; class: study this at home!]
```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 . . . */
}
```
[lecturer: briefly or can skip; class: study this at home!]
```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 log2(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)
Code: ..../C/List/ for linked lists, ..../C/Sort/ for arrays

## 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

Another idea: partition the array:
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
[an efficient quick sort; class: study this at home!]
```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(n2)-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
© L.Allison, Sunday, 28-Nov-2021 04:45:43 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/06sort3.shtml
Computer Science, Software Engineering, Science (Computer Science).