Training Trains Internship
Student login
← Algorithm Design learning path
Algorithm Design · Module 8 of 10

Sorting and searching in depth

Compare sorting algorithms and their trade-offs.

📖 Key ideas

  1. Comparison sorts: bubble, insertion, selection (O(n²)); merge, heap, quick (O(n log n)).
  2. Lower bound for comparison sorting: Ω(n log n).
  3. Non-comparison sorts: counting, radix, bucket (linear under conditions).
  4. Stable sorts keep equal elements in order.
  5. Binary search variants find first/last occurrence or answer bounds.
💡 Real-life example: Choosing a sort is choosing transport: bicycle for a short trip (insertion), train for long distances (merge).
Stable sortKeeps equal elements' order
In-placeUses O(1) extra memory
Counting sortSorts by counting values
Lower boundBest possible complexity