Outline

Heap Sort

insert all the elements into a heap
remove all the elements from a heap
since the heap grows from the left of the array, insert the elements from left to right, making room for each new element by removing it from the array just as the heap needs the additional space
in-class exercise: given a method to insert items into a heap, write a method to insert all the elements of an array into a heap
since the heap shrinks from the right of the array, the element removed from the heap can be put back into the array just to the right of the heap
in-class exercise (individually): given a method to insert items into a heap and a method to remove items from a heap, write a heapsort method
each insertion and removal takes at most time O(log n), so heapsort takes at most O(n log n), and space n

given an array to sort, pick an arbitrary element, called a pivot
arrange all the elements so everything smaller than the pivot is to the left of the pivot, and everything larger than the pivot is to the right of the pivot
this can be done in a single pass through the array:
1. select the first array element as the pivot, and set index p = 0
2. set index first = 1, last = array.length - 1
3. while (array[first] < pivot) first++;
4. while (array[last ] > pivot) last--;
5. now array[first] > pivot and array[last] < pivot, so swap array[first] and array[last]
6. go back to step 3 until all elements < pivot are to the left of all the elements > pivot (and first == last)
7. swap array[p] and array[first] to put the pivot in between
consider the sub-arrays to the left of the pivot and to the right of the pivot
if these sub-arrays were sorted, the entire array would be sorted
the sub-arrays can be sorted by calling quick-sort recursively
if the pivot is approximately in the middle, the depth of recursion will be O(log n)
at each depth of recursion, the total amount of work done is O(n) to rearrange the array to the left and right of the pivot
so with good pivot selection, quicksort is O(n log n)
with random pivot selection, quicksort is O(n log n)
by selecting the smallest possible pivot, e.g. if the array is already sorted, the depth of recursion is O(n), and quicksort is O(n²)

named after Donald Shell
tries to do insertion sort on nearly-sorted arrays, when insertion sort is most efficient
divide array into sub-arrays of 2 or 3 elements
sort the sub-arrays
combine the sub-arrays in sorted order
subtlety: sub-arrays are not adjacent, they are the collection of elements separated by gap
intuitively, the array can be thought of as being re-arranged into gap rows of n/gap columns, but without moving the data in the array
each column is sorted (in place in the array) using insertion sort
this can move data quickly towards its final position in the array
selecting the gap affects the performance of the algorithm
for good performance, the initial gap can be floor(n/2), subsequent gaps floor(gap/2.2) (but not less than 1)

set the gap as described above
the first sub-array consists of a[0], a[0+gap], and possibly a[0+gap+gap]
the second sub-array consists of a[1], a[0+gap], and possibly a[1+gap+gap]
perform insertion sort on each sub-array
update the value of the gap as described above
the first sub-array consists of a[0 + n * gap] for all values of n which give valid indices in the array
the second sub-array consists of a[1 + n * gap], and so on
after the sort, when gap==1, the array is sorted

insertion sort works well on nearly-sorted arrays
shell sort is better than straight insertion sort, because it applies insertion sort to nearly-sorted arrays
if the gap is a sequence of numbers of the form 2^k-1 (for decreasing k, e.g. 31, 15, 7, 3, 1), the performance is O(n^3/2), that is, O(n sqrt(n))