Course contentsShow
← Computer Science
Lesson 748 of 2,87218. Sorting AlgorithmsFree lesson

Insertion Sort: Analysis

Analyzing insertion sort's O(n²) worst case, O(n) best case for nearly sorted data, and stable in-place properties.

Insertion Sort: Analysis

You'll learn: How insertion sort performs in best, average, and worst-case scenarios, and why it's useful for nearly sorted data.

Understanding Insertion Sort's Performance

Insertion sort's efficiency varies dramatically based on input characteristics. Unlike algorithms that always take the same time regardless of input order, insertion sort's performance depends on how sorted the data already is.

Time Complexity

Worst Case: O(n²)
When the array is in reverse order, every element must be compared and shifted past all previously sorted elements. For the second element, you make 1 comparison; for the third, 2 comparisons; and so on. This creates the sum 1 + 2 + 3 + ... + (n-1) = n(n-1)/2, which simplifies to O(n²).

Best Case: O(n)
When the array is already sorted (or nearly sorted), each element only needs one comparison to confirm it's in the right place—no shifting required. You simply scan through the array once, making it linear time.

Average Case: O(n²)
On random data, on average, each element shifts halfway through the sorted portion, still resulting in quadratic time.

Space and Stability

Space: O(1)
Insertion sort is in-place—it sorts within the original array using only a constant amount of extra memory for temporary variables.

Stability: Stable
Equal elements maintain their relative order because we only shift an element leftward when it's strictly less than its neighbor, never when equal.

Practical Considerations

Insertion sort shines on small datasets (typically n < 10-50) and nearly sorted data. Many advanced algorithms like Timsort use insertion sort as a subroutine for these cases. Its simple implementation and low overhead make it faster than O(n log n) algorithms on tiny inputs.

Key Takeaway: Insertion sort runs in O(n²) worst case but achieves O(n) on nearly sorted data, making it stable, in-place, and practical for small or partially ordered inputs.