Algorithms - Sorting - Lecture 2

Bubble sort

Insertion sort

Stable vs unstable sorting: whether you keep equal elements in their original order; important for some applications, like for Radix sort

Inspired by sorting boolean arrays, we can see there should be a n log n algorithm

$O(n\log{n})$ sorts

nlogn is a lower bound for sorting nice proof using Decision trees

Merge sort

Heap sort

Quicksort

Counting sort, trying to make sort work on linear time. But need to assume something about the data. In particular, we assume that there's a finite number of values that can appear in the array.

Bucket and radix sort extend this idea

Bucket sort

Radix sort