Sorting

Insertion Sort

Builds the sorted array one item at a time by inserting each new element into its correct place among the already-sorted prefix.

BestO(n)

AverageO(n²)

WorstO(n²)

SpaceO(1)

First element is trivially sorted.

Size16

100

Comparing

Swap / write

Key / cursor

Pivot

Sorted

1 / 89

Speed6 fps

1void insertionSort(int[] arr) {2  for (int i = 1; i < arr.length; i++) {  // grow sorted prefix3    int key = arr[i];  // element to insert4    int j = i - 1;5    while (j >= 0 && arr[j] > key) {  // shift bigger ones right6      arr[j + 1] = arr[j];7      j--;8    }9    arr[j + 1] = key;  // drop key into the gap10  }11}

More algorithms

Bubble Sort Selection Sort Quick Sort Merge Sort Heap Sort Shell Sort Cocktail Shaker Sort

Loading…