PROWAREtech

C/C++: Insertion Sort Algorithm

Insertion sort is the fastest of the O(n²) 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];
			j--;
		}
		array[j] = temp;
	}
}

Comment