Sorting Notes

A brief summary of the three main AP sorting methods.

Time: 2 days.

  • Day 1: Implement sorting algorithms.
  • Day 2: Implement searching, quiz.

Searching

“Binary search”. (Higher/lower/got it.)

Selection Sort

  • Find the smallest, move it to the front.
  • Triangle pattern for comparisons - kind of slow.
  • Never any faster (cannot get lucky).

Insertion sort

  • Build up a sorted list at the start of the array.
  • Can be fast if input is mostly sorted.

Merge sort

Recursive. Build up from small sorted lists to big.

Tool 1: merge sorted

Cool fact: joining (“merging”) two sorted arrays is fast.

// input: two sorted arrays
// output: one sorted array with all items from both
int[] merger(int[]xs, int[] ys)

Tool 2: recursion

  • Recursively break down the arrays until n=1.
  • merger to rebuild in sorted order

Signature:

int[] mergesort(int[] nums)

Suggested Approach to Mergesort

  1. Write merger.
  2. Make mergesort_v1 which breaks the list into two pieces and then sorts each piece with selectionSort and merges the results.
  3. Make mergesort by just swapping out selectionSort for a recursive call to mergesort

Coding Tools

Do not worry about making lots of copies of arrays, especially when writing mergesort. Focus on the big picture ideas.