Video · + 1 min read

Selection Sort

Given an array AA of size nn, the selection sort iterates through indices 0≤k<n0\le k<n, at each step finding the minimum element of the sub-array A[k,n)A[k,n) and swapping its position with A[k]A[k]. See the following example of the selection sort:

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

This is O(n2)O(n^2) since in the worst case you will have to search n+(n−1)+⋯+1=n(n+1)2=O(n2)n+(n-1)+\dots+1=\frac{n(n+1)}2=O(n^2).

Animated selection sort of ten digits shown in a column; the first frame, still unsorted, reads 8, 5, 2, 6, 9, 3, 1, 4, 0, 7.

The selection sort algorithm.

Insertion Sort

The insertion sort iteratively sorts the first kk elements of the array, by finding what position the next element should go. This is O(n2)O(n^2) because in the worst case, the array starts sorted in the opposite direction, so you need to make at most 1+2+⋯+n=n(n+1)2=O(n2)1+2+\dots+n=\frac{n(n+1)}2=O(n^2) swaps.

Animated insertion sort of eight digits in a row; the first frame, still unsorted, reads 6, 5, 3, 1, 8, 7, 2, 4.

The insertion sort algorithm.

Merge Sort

Merge sort is a recursive sort that splits an array in two halves and sorts each half, then merges the two sorted components together. Try proving that merge sort runs in O(nlog⁡n)O(n\log n)!

Animated merge sort of eight digits in a row; the first frame, still unsorted, reads 6, 5, 3, 1, 8, 7, 2, 4.

The merge sort algorithm.

Beyond

Finally, here is a cute little video to show you some of the sorting algorithms.

Type a concept, like “slope” or “photosynthesis”.

↑ ↓ to choose · Enter to openSearch explanations and problems