Sorting Algorithms

The built-in sort is fast, but writing a sort yourself teaches how algorithms think. Insertion sort grows a sorted section one item at a time: O(n^2), simple, and quick on small or nearly sorted arrays. Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves: O(n log n) every time.

How it reads

• merge always takes the smaller front item of the two sorted arrays
• mergeSort splits until each piece has one item
• The pieces are merged back up, level by level

Cloud tip: In real code, use sort with a compare function. Writing your own is for learning and for special cases.