OutlineAnnouncement: out of town Thu 11/8, Tue 11/13, Tue 11/20There will be guest lectures: John Umbaugh and Chris KiekentveldNo office hours Thu 11/8, Fri 11/9, Tue 11/13, Tue 11/20Last time: Sorting• Selection sort• Heap sort• Insertion sortToday: More sorting• Insertion sort optimizations• Merge sortSugih Jamin ([email protected])Insertion SortAlgorithm (see Fig. 15.2):• given a “pile” of items in an array• insert into an already sorted array one item at a time using linearsearch• non-adaptive version: continues linear search till end of sorted array• adaptive version: stops linear search once an insertion point hasbeen foundContrast to selection sort:• selection sort: select item from pile in order, add to the front (end) ofsorted list• insertion sort: pick next item from pile, insert in order into sorted listSugih Jamin ([email protected])Insertion SortSort array a[5, 2, 3, 8, 5, 1]:Non-adaptive:voidisort_na(int *a, int N)Is it stable?Adaptive:voidisort_a(int *a, int N)Is it stable?Sugih Jamin ([email protected])Running Time and OptimizationsRunning time:“Optimizations”:• binary search instead of linear search?• move instead of swap: saves O(n2) copies• use of sentinel: saves O(n2) CMPsSugih Jamin ([email protected])Insertion Sort: Move Instead of SwapSlide items down instead of swapping them,to move down k steps, only need k + 2 copies instead of 3k copiesSort array a[5, 2, 3, 8, 5, 1]:voidisort_am(int *a, int N)Saves O(n2) copies, but total running time is still O(n2)Is it stable?Sugih Jamin ([email protected])Insertion Sort: Use of SentinelSort array a[5, 2, 3, 8, 5, 1]:Can use sentinel to doO(n2) less comparisons• move smallest item to theleftmost position (O(n)operation)• then it’s not necessaryto check (j > 0) in theinner loop (saves O(n2)CMPs)Total running time is stillO(n2)voidisort_as(int *a, int N){int i, j, tmp;for (j = 1, i = j+1; i < N; i++) {if (a[j] > a[i]) {j = i;}} /* now move smallest to a[0] */if (a[0] > a[j]) swap(a[0], a[j]);for (i = 2; i < N; i++) {for (j = i, tmp=a[i];a[j-1] > tmp; j--) {a[j] = a[j-1];}a[j] = tmp;}return;}Sugih Jamin ([email protected])InversionA sorted list is but a permutation of an unsorted oneLet S = {1, 2, 3, . . . , n} and P = {p1, p2, . . . , pn} be a permutation of SAn inversion in P is a pair of items (pi, pj) where pi> pjbut i < j,e.g., P = {1, 4, 3, 2} has 3 inversions: (4, 3), (4, 2), (3, 2)The job of a sorting algorithm is to “correct” inversions!Sugih Jamin ([email protected])Insertion Sort Average Running TimeLet PRbe P in reverse, i.e., PR= {pn, pn−1, . . . , p2, p1}A pair of items (pi, pj) is either an inversion in P or in PR,with equal probabilityThere aren2=n(n−1)2pairs in a sequence of n itemsOn average, we expectn(n−1)/22=n(n−1)4inversions in a givensequence PInsertion sort corrects one inversion at a time, so the average runningtime of insertion sort isn(n−1)4= O(n2)Sugih Jamin ([email protected])Merge SortSort a[85 24 63 45 17 31 96 50] using merge sort[85 24 63 45 17 31 96 50][85 24 63 45] [17 31 96 50][85 24] [63 45] [17 31] [96 50][85] [24] [63] [45] [17] [31] [96] [50][24 85] [45 63] [17 31] [50 96][24 45 63 85] [17 31 50 96][17 24 31 45 50 63 85 96]Sugih Jamin ([email protected])Merge SortAlgorithm (see Preiss Fig. 15.10):• spilt list into two roughly equal parts• mergesort each part recursively• merge the two sorted partsvoidmergesort(int *a, int left, right){int mid;if (left <= right) return;mid = (left+right)/2;mergesort(a, left, mid);mergesort(a, mid+1, right);merge(a, left, mid, right);return;}Sugih Jamin ([email protected])MergeSplitting list into two roughly equal parts is easyHow to merge the two sorted parts?Simplest way: use scratch space of equal size (see Preiss Fig. 15.9)voidmerge(int *a, left, mid, right)Running time of merge:Need an extra O(N) space, which may not be available for large data setor small devices (handhelds, e.g.)Sugih Jamin ([email protected])Merge SortRecurrence relation:Running time:Disadvantages:• Non-adaptive: for pre-sorted sequence, worse than insertion sort!• Not in-place: needs an extra O(n) space, with attending copyoperation, so slower than other O(n log n) sort• Stack space: recursion uses up O(log n) stack spaceAdvantage: can be stable if merge() is stableSugih Jamin ([email protected])Removing Recursion: Iterative Merge SortBottom-up:• consider original list as Nsublists of size 1• scan thru list performing1-by-1 mergers to pro-duce N/2 ordered sub-lists of 2 elements• scan thru list performing2-by-2 mergers to pro-duce N/4 ordered sub-lists of 4 elements• etc.voidimsort(int *a, left, right){int size, i, n;for (size = 1, n = right-left;size <= n; size *= 2) {for (i = left; i <= right-size;i += 2*size) {merge(a, i, i+size-1,min(i+2*size-1,right));}}return;}Sugih Jamin ([email protected])Inefficiencies of merge()From merge(int *a, left, mid, right):1 for (i=k=left, j=mid+1; k <= right; k++) {2 if (i > mid) { a[k] = tmp[j++]; continue; }3 if (j > right) { a[k] = tmp[i++]; continue; }4 a[k] = ( tmp[j] < tmp[i] ) ? tmp[j++] : tmp[i++];5 }The boundary checks in lines 2 and 3 return false most of the time. Canwe remove them by using a sentinel as in insertion sort?Sugih Jamin ([email protected])Insertion Sort: Use of SentinelSort array a[5, 2, 3, 8, 5, 1]:Can use sentinel to doO(n2) less comparisons• move smallest item to theleftmost position (O(n)operation)• then it’s not necessaryto check (j > 0) in theinner loop (saves O(n2)CMPs)Total running time is stillO(n2)voidisort_as(int *a, int N){int i, j, tmp;for (j = 1, i = j+1; i < N; i++) {if (a[j] > a[i]) {j = i;}} /* now move smallest to a[0] */if (a[0] > a[j]) swap(a[0], a[j]);for (i = 2; i < N; i++) {for (j = i, tmp=a[i];a[j-1] > tmp; j--) {a[j] = a[j-1];}a[j] = tmp;}return;}Sugih Jamin ([email protected])Merge Using Bitonic Sortvoidbsmerge(int *a, left, mid, right){int i,j,k,tmp[MAXN];memcpy(tmp, &a[left], mid-left+1);for (k = mid-left+1, j = right; j > mid; j--, k++)tmp[k] = a[j]; /* copy in reversed order */for (i=k=left, j=right; k <= right; k++) {a[k] = ( tmp[j] < tmp[i] ) ? tmp[j--] : tmp[i++];}return;}But bsmerge is not stable. Why?Sugih Jamin ([email protected])In-place Merge SortHuang and Langston (1988) has a version of in-place merge(http://www.cs.utk.edu/ langston/courses/cs594-fall2003/HL.pdf)but it is very slowAlternatively, Katajainen, Pasanen, and Teuhola (1996) does