CMPT 125 Lecture Notes - Lecture 9: Merge Sort, Comparison Sort, Insertion Sort
18 Dec 2018
School
Department
Course
Professor
Document Summary
Running time o(n log(n)) for good pivots. More efficient than quadratic sorts (selection sort, insertion sort) In-place comparison sort, i. e. , requires o(1) additional memory. Running time o(n log(n)) worst case. It is very efficient for arrays sets that are already substantially sorted. O(n) is rearranging. n-1 elements biggers than pivot. n + (n-1) + (n-2) + 2 + 1 = o(n2) T(n) = 2*t(n/2) + t(merge n elements) If array is already sorted t(merge n elements) = o(n) Each element is moved at most log2(n) times. Each element is swapped once in each merging procedure. The size of the array containing the element is divided by two each time, So the number of times an element appears in a (total) merging procedure is log2(n) Therefore, each element is swapped log2(n) times. Therefore, the total running time is o(n*log2(n)) 3rd line: n-2 n + (n-1) + (n-2) + 2 + 1 = n(n+1)/2 = o(n2)
