Insertion Sort

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 = pparray[i];
		unsigned int j = i;
		while (j > 0 && temp < pparray[j - 1]) {
			pparray[j] = pparray[j - 1];
			j--;
		}
		pparray[j] = temp;
	}
}