Insertion Sort

Watch each element slide into its correct position within the already-sorted prefix.

Build the sorted array one element at a time by inserting each new element into its correct position within the sorted prefix.

Time O(n²) | Space O(1) | Stable | In-place

Data

Size15

Speed800ms

default

comparing

swapping

sorted

key

for i = 1 to n-1:

  key = arr[i]

  j = i - 1

  while j >= 0 and arr[j] > key:

    swap(arr[j], arr[j+1])

    j = j - 1

  // key is in position

// array is sorted

n = 15

>Press SORT to begin…