Computer Science CS50 Lecture Notes - Merge Sort, Insertion Sort, Quicksort
2 Jul 2022
School
Department
Course
Professor
Document Summary
Mergesort has too much overhead for tiny subarrays. Cutoff to insertion sort for 7 items. 26 assert issorted(a, lo, hi); public static void sort(comparable[] a) { Comparable[] aux = a. clone(); // duplicate a to aux sort(a, aux, 0, a. length-1); assert issorted(a); Pass through array, merging subarrays of size 1. Repeat for subarrays of size 2, 4, 8, 16, . A stable sort preserves the relative order of items with equal keys. The second sort changed the order of the students of section 3. To check whether a sort algorithm is stable or not is to check if it has long-distance exchange. Selection sort: select the minimum to the front, which is big step and by-pass the equal items. Partition so that, for some j entry a[j] is in place no larger entry to the left of j no smaller entry to the right of j. Number of compares is ~ n lg n.
