Sorting
Internal sort  - in main memory (no files)
Stable sort, elements with equal keys retain order
In situ sort, minimal memory needed beyond that to hold N elements

Sorting is usually either O(N2) or O(NlogN)
O(N2) Sorting
Selection sort    
For each element
Search remainder of array
Exchange every time a smaller value is found
“O”?
Can we make it faster?

O(N2) Sorting
Bubble sort
Exchange adjacent elements as needed
Ends when no exchange needed

“O”?


O(N2) Sorting
Linear insertion sort
Add new element at end of array
Exchange with preceding element as long as necessary

“O”?
O(NlogN) Sorting
Merge sort
Requires “helper” array

“O”?
O(NlogN) Sorting
Heap sort
Views array as heap
A(1) is a heap
Add rest of array one element at a time, keeping it a heap
Exchange root with rightmost lowest leaf, heap is now almost heap
Prune rightmost lowest leaf
Re-heap

“O”?
O(NlogN) Sorting
quicksort
Recursive idea
Partition array around “median” (every element in “higher” array greater than every element in “lower”
Repeat
What’s wrong?
“pivot” stands in for median
Up cursor moves from left through all elements less than pivot
Down cursor does converse

O(NlogN) Sorting
Quicksort (cont.)
When cursors “stop”
Exchange elements
If they collide?
Partition into 2 arrays at that point
Repeat until?

“O”?