Quick sort
High level code are quite simple ( divide/conque, recursively partition the array):
void
quickSort(
int
arr[],
int
low,
int
high)
{
if
(low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int
pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
The key is how to partition in-place?
Here a pretty good quick sort ( random pivot ) video , keep l, r index
There are some other partition strategy like always choose the last or first element.
http://www.geeksforgeeks.org/merge-sort/