Insertion Sort - Complexity & Comparison

Complexity Analysis

Insertion sort has different performance depending on input order.

Time Complexity

Best Case: O(n)

• Array is already sorted
• Inner loop runs once per element (just checks)
• Linear time - very efficient

Average Case: O(n²)

• Random array order
• Inner loop runs about n/2 times on average
• Quadratic time

Worst Case: O(n²)

• Array is reverse sorted
• Inner loop runs maximum times
• Every element needs maximum shifting

Space Complexity

O(1) - Constant Space

• Only uses a few variables
• In-place sorting
• No extra arrays needed

Why O(n²) Average?

• Outer loop: Runs n-1 times
• Inner loop: Runs about i/2 times on average for each i
• Total: Sum of 1 + 2 + … + (n-1)/2 ≈ n²/4 = O(n²)

Comparison with Other Algorithms

When to Use Insertion Sort

Insertion sort is ideal when:

✅ Small datasets (< 50 elements)
✅ Nearly sorted arrays (best case O(n))
✅ Stability required (maintains order of equal elements)
✅ Simple implementation needed (easy to code)
✅ Educational purposes (teaching sorting concepts)

When NOT to Use

❌ Large unsorted arrays (use quicksort/mergesort)
❌ Random data (O(n²) performance)
❌ Performance critical (use faster algorithms)

Real-World Usage

• Small arrays: Many libraries use insertion sort for small sub-arrays
• Hybrid algorithms: Timsort uses insertion sort for small chunks
• Nearly sorted data: Very efficient when data is mostly sorted
• Online algorithms: Can sort data as it arrives

What’s Next?

Let’s test your understanding with practice problems and a quiz.