Sorting Notes

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.

• Arrays.copyOfRange(int[] original, int from, int to) uses the convention “include the start, exclude the end”, the same as substring.