← Public decks·Computer Science

Sorting Algorithms: Time Complexity Cheatsheet

Classic sorting algorithms — average/worst time, space, and stability for interview recall.

10 cards· by GuruOwl

Make a deck like this from your own PDF — free.

Try it
  1. 01
    What is the average and worst-case time of mergesort?
    Both Θ(n log n). Extra space Θ(n). Stable.
    mergesort
  2. 02
    What is the average time of quicksort? Worst case?
    Average Θ(n log n); worst Θ(n²) (bad pivots). Typical in-place variants use Θ(log n) stack space. Not stable (typical).
    quicksort
  3. 03
    What is heapsort’s time complexity?
    Θ(n log n) time, Θ(1) auxiliary space (array heap). Not stable.
    heapsort
  4. 04
    What is insertion sort’s best and worst case?
    Best Θ(n) (already sorted); worst Θ(n²). Stable; excellent for small/nearly sorted arrays.
    insertion
  5. 05
    What is selection sort’s time complexity?
    Θ(n²) always. Not stable (typical). Minimal swaps.
    selection
  6. 06
    What is bubble sort’s time complexity?
    Worst/average Θ(n²); best Θ(n) with early exit if no swaps. Stable.
    bubble
  7. 07
    What does it mean for a sort to be stable?
    Equal keys keep their original relative order.
    stability
  8. 08
    Lower bound for comparison-based sorting in the worst case?
    Ω(n log n) — decision-tree bound.
    theory
  9. 09
    When can counting/radix sort beat n log n?
    When keys have limited range/structure (integer keys with fixed digits) — not pure comparison sorts.
    linear-time
  10. 10
    Which common O(n log n) sorts are stable?
    Mergesort is the standard stable O(n log n) example; heapsort/quicksort typically are not.
    stability