Using
int
for indexing is wrong. Usestd::size_t
.An addition in
int q = (p + r) / 2;
may overflow. Considerint q = p + (r - p)/2;
A single most important advantage of merge sort is stability: element compare equal retain their original order. In your implementation
if(left_sub[i] < right_sub[j])
stability is lost: of the two equals the one from the right is merged first. It doesn't really matter for integers, but still
if(left_sub[i] <= right_sub[j])
is a correct way.
As the partitions get smaller and smaller, a recursion overhead of quick sort becomes more and more expensive. Do not recurse into small partitions; have a final pass of an insertion sort instead, like in:
void quick_sort_helper(int* arr, int low, int high) { if (low + CUTOFF < high) { int partition_index = partition(arr, low, high); // partition the array and get the partition index quick_sort_helper(arr, low, partition_index - 1); // recursively sort the left subarray quick_sort_helper(arr, partition_index + 1, high); // recursively sort the right subarray } } void quick_sort(int* arr, int size) { quick_sort_helper(arr, 0, size - 1); insertion_sort(arr, 0, size - 1); }
Selection of a cutoff value is an interesting question. Insertion sorting an arbitrary array has a quadratic time complexity; however we are guaranteed that by the time
insertion_sort
is called, the array is almost sorted. Every element is within aCUTOFF
of its final destination. The time complexity becomesO(n * CUTOFF)
. Since we are striving to obtain anO(N * log n)
complexity,log n
is a natural choice.That said, most implementation use a cutoff constant like 16 or 32.