Hi,

Replacing the bubble sort with insertion sort gives an 80% reduction in runtime on average (with randomized keys) for small partitions.

If the keys are pre-sorted, insertion sort runs in linear time, and even if the keys are reversed, insertion sort is faster than bubble sort, although not by much. See below for measurements.

Suggested by: Pieter de Goeje