CS205

Insertion Sort

O(n²)

Builds the sorted array one element at a time by inserting each element into its correct position.

Insertion Sort
64
34
25
12
22
11
90
0
1
2
3
4
5
6
Ready to start
Step 0 of 0
Speed:500ms
Default
Comparing
Swapping
Sorted
Pivot
Algorithm Info

Builds the sorted array one element at a time by inserting each element into its correct position.

Best Case
O(n)
Average Case
O(n²)
Worst Case
O(n²)
Space
O(1)
How It Works
  1. Start with the second element (first element is "sorted")
  2. Take the current element and compare it with elements in the sorted portion
  3. Shift larger elements one position to the right
  4. Insert the current element in its correct position
  5. Move to the next element and repeat
  6. Continue until all elements are in the sorted portion
Pseudocode
for i = 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j - 1
    arr[j+1] = key
Complexity Analysis
Time Complexity
Best:O(n)
Average:O(n²)
Worst:O(n²)
Space Complexity
O(1)
Stable Sort?
Yes
Advantages & Disadvantages
Advantages
  • Simple and intuitive - like sorting cards in your hand
  • Efficient for small datasets
  • Very fast for nearly sorted arrays - O(n)
  • Stable sort - preserves order of equal elements
  • In-place and online (can sort as data arrives)
Disadvantages
  • Slow for large datasets - O(n^2)
  • Many element shifts required for reverse-sorted data
  • Not suitable for random large arrays
When to Use Insertion Sort
  • •Small arrays (typically < 50 elements)
  • •Nearly sorted data - very efficient
  • •Online sorting - data arrives incrementally
  • •Hybrid algorithms (used in Timsort for small runs)
  • •When stability is required