Lab 6

QuickSort

Add items to array that are in the correct "half" of the array, may be out of order

Now, recurse into both halves, make a new pivot in each subgroup

• The "halves" are not necessary equal
• QuickSort could be O(n^2) in worst case, but usually never happens
• Keeping track of the median makes it much better, but finding the median takes a bit of work
  • You could keep track of three values(beggining, middle, end), and then get elements

MergeSort guarantees each half is exactly half of the total array

Stable sorting algorithm: sorts on all levels, two 2's are treated differently based on other factors

• Preserves order

Unstable sorting algorithm: isn't guaranteed to preserve order