Sorting algorithms

Python's sorted() is fast, but writing a sort yourself teaches how algorithms think. Insertion sort grows a sorted section one item at a time, sliding each new item left into place: O(n^2), simple, and quick on small or nearly sorted lists. Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves: O(n log n) every time.

How it reads

• merge walks two sorted lists at once, always taking the smaller front item
• merge_sort splits until lists have one item, which are already sorted
• Then it merges back up, level by level

Cloud tip: In real code, call sorted(). It uses Timsort, a hybrid of merge sort and insertion sort tuned for real-world data.