articles » current » c-plus-plus » algorithms » insertion-sort

C/C++: Insertion Sort Algorithm

An O(n²) at worst algorithm and a friend to the Quick Sort algorithm.

Insertion sort is the fastest of the O(n2) algorithms. It's an impressive little algorithm for sorting small arrays. Use it to sort the smaller subarrays in quick sort giving approximately a 20% performance increase.

See the Algorithm Study for more details.

 // insertion sort algorithm
void insertion_sort(int array[], const unsigned int size) {
	for (unsigned int i = 1; i < size; i++) {
		int temp = array[i];
		unsigned int j = i;
		while (j > 0 && temp < array[j - 1]) {
			array[j] = array[j - 1];
		array[j] = temp;

This site uses cookies. Cookies are simple text files stored on the user's computer. They are used for adding features and security to this site. Read the privacy policy.