Insertion Sort

Takes the numbers one by one and inserts each into its place in the already sorted part, shifting bigger numbers to the right. Very fast for almost sorted data.

Podstawowy

O(n^2)O(1)BOBRALEMOZGIINSTALOGIK

Select programming language

Choose the language in which you want to trace insertion sort.

Select array

Sorted array: no shifts at all (best case). Reversed: every number travels to the very front (worst case). You can also type your own numbers.

Insertion Sort (Python): [5, 2, 4, 6, 1, 3]

Array

1/0

Animation speed1.0x

Source codePython
1def insertion_sort(arr):
2    n = len(arr)
3    for i in range(1, n):
4        key = arr[i]
5        j = i - 1
6        while j >= 0 and arr[j] > key:
7            arr[j + 1] = arr[j]
8            j -= 1
9        arr[j + 1] = key
10    return arr
11
12arr = [5, 2, 4, 6, 1, 3]
13sorted_arr = insertion_sort(arr)
14print(sorted_arr)

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	def insertion_sort(arr):
2	n = len(arr)
3	for i in range(1, n):
4	key = arr[i]
5	j = i - 1
6	while j >= 0 and arr[j] > key:
7	arr[j + 1] = arr[j]
8	j -= 1
9	arr[j + 1] = key
10	return arr
11
12	arr = [5, 2, 4, 6, 1, 3]
13	sorted_arr = insertion_sort(arr)
14	print(sorted_arr)