I have just read a chapter about sorting. I am now writing down everything I remember. Do not read this just yet... It is not edited, I haven't yet gone back to fill in holes in my understanding. This is to prime my brain to remember shit.

Sorting

• Many algorithms use sorting as a building block.

• To understand these algorithms later on requires an understanding of sorting.

• In general, we study sorting on numbers, but we can sort anything provided we can define a pairwise comparison operation between two elements.

  • As in, if we can define a method that specifies whether $a < b$, $a > b$, or $a = b$ for any type or value of $a$ and $b$ then we are golden.

• There are five main algorithms that I remember for sorting:

  • Naive sort (idk)
  • Insertion sort
  • Merge sort
  • Quick sort
  • Bucket sort

• I don't remember the first sort

• I barely remember insertion sort

• Merge sort

  • NOTES: This is a Divide and Conquer Algorithm (problem is reduced recursively into smaller problems of the same type)
  • ABSTRACT: Split array in half, sort each half, merge results together recursively.
  • THE METHOD: We split an unsorted array into two halves, recurse on each half.
  • When we reach one element arrays, we say they are sorted.
  • We then apply a merge operation on both of the sorted arrays defined as such:
    • compare the top-most elements of ea. array (they are in sorted order) using our comparison function.
    • grab whichever element wins based on the way you are sorting and repeat for the rest of the elements until both arrays are done.
    • repeat until you only have one array
  • DONE!

• Quick sort

  • NOTES: This is a randomized, expected-time algorithm (we expect it to perform well in most-cases (AND IT DOES! (usually)))
  • ABSTRACT: Same as merge sort, but with explicitly chosen median element called the pivot.
  • THE METHOD: We pick a random element and call it our pivot $p$.
  • We then segment our array into three parts, before the pivot, the pivot itself, and after the pivot.
  • When we reach one element arrays, there is only one possible pivot and we call it sorted.
  • We then merge the arrays together in the same way as merge sort placing these sorted arrays before or after our pivot based on the comparison operation we define.

• Bucket sort

  • NOTES: This one is intuitive. Assumes your input is random (by random I mean evenly distributed across the distribution)
  • ABSTRACT: Make $k$ buckets for $n$ items on some property of the input. Sort ea. item into one of these buckets. Nest buckets as you see fit.
  • THE METHOD: Do a linear scan through all items and create buckets. If we are working with names, we might have 26 buckets one for each letter of the alphabet.
  • On your pass, put each item into its respective bucket. If multiple names fit into one of the buckets, you can optionally nest buckets. as in:

    A	B	C	...	Z
    AA	BE, BR	CA	...	ZO
    Aaron	Ben, Brian	Carter	...	Zoey