Insertion Sort

sorting

Click Generate New or press Play

Step 1 / 1

Ready

Speed

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

Time Complexity

Best

\mathrm{O}\left(n\right)

Avg

\mathrm{O}\left(n^{2}\right)

Worst

\mathrm{O}\left(n^{2}\right)

Max Operations

Worst-case bound

\frac{n(n-1)}{2}

Used for efficiency calculation in Stats Panel

Space Complexity

Aux

\mathrm{O}\left(1\right)

In-place — key variable + indices only

Pseudocode

1procedure insertionSort(A: list)

2for i = 1 to n do

3key = A[i]; j = i - 1

4while j >= 0 and A[j] > key do

5A[j+1] = A[j]

6j = j - 1

7A[j+1] = key

8end for