CSC 226 Lecture Notes - Lecture 2: Sorting Algorithm, Integer Sorting, Merge Sort
Document Summary
Csc 226 algorithm based that sorts based only on comparisons elements to be sorted satisfy total order properties. Input order has no effect on the efficiency of the algorithm. Great for data that has a good bit of it already sorted. Updates sort as values are received: as data that wasn"t originally there is added to the algorithm, insertion sort can handle it easily. Using a pivot, values smaller than pivot are sent to the left of pivot and values larger than pivot are sent to the right of pivot. Done recursively for the left and right sides of pivot until sort is completed. Best-case = o(nlogn) some say that it"s actually on, they use different partitioning schemes that we don"t in the class. Best algorithm in practice, better than merge sort which is supposedly faster in theory. Dividing elements until you reach base cases, then merging them.