Track 16 · Lesson 4 of 12

Sorting algorithms

Understand how selection, insertion and merge sort work and what they cost, then use sorted() with stable keys in practice.

You will be able to

• Trace selection sort and insertion sort and explain why they are O(n²)
• Merge two sorted lists in linear time and build merge sort from that step
• Explain what a stable sort is and use stability to sort by several criteria
• Choose sorted() or list.sort() with a key function for real work