Back to list

Insertion Sort

Builds the final sorted array one item at a time. Efficient for small data sets.

Initial ArrayItems: 8
23
0
64
1
37
2
91
3
85
4
81
5
33
6
12
7
Sorted Region
Key (Floating)
Shifting
Speed
Comp
0
Shifts
0
Array Controls

Time Complexity

Best
O(n)
Avg
O(n²)
Worst
O(n²)

Very efficient for small or nearly sorted datasets. Worst case is reverse sorted.

Space Complexity

Auxiliary SpaceO(1)

Insertion sort sorts the array in-place.

Algorithm Details

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

How it works

  1. Iterate from arr[1] to arr[n] over the array.
  2. Compare the current element (key) to its predecessor.
  3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Complexity

  • Time Complexity: O(n²)
  • Space Complexity: O(1)