Quicksort is a sorting algorithm. It is used frequently.

Quicksort also uses “divide-and-conquer”.

Empty arrays and arrays with just one element are the base case. For both situations, you only return the arrays as is, since there will be nothing to sort.

You pick an element from the array that will be the “pivot”. Then, you find the elements smaller and the ones larger than it. That is called partitioning. Then, you will have: . A sub-array with the numbers less than the pivot . The pivot . A sub-array with the numbers greater than the pivot Both sub-arrays are not sorted, just partitioned.

Inductive proofs are one way to prove that an algorithm works. Each inductive proof has 2 steps: the base case and the inductive case.

Regarding Big-O notation, quicksort at the worst case takes O₍n²) time. In the average case, it takes O₍n log n) time. The worst case is if you choose the first element as the pivot.

When you write Big-O notation like O₍n₎, the “n” part in fact means “c * n”. “c” is a fixed amount of time an algorithm takes. “c” means “constant”. You usually ignore that constant, because if 2 algorithms have different Big-O times, the constant does not matter.

But sometimes the constant matters. Quicksort VS Mergesort is an example. Quicksort has a smaller constant than Mergesort. So, if they’re both O₍n log n₎ time, quicksort is faster. And, in practice, quicksort is faster because it hits the average case more often than the worst case.

The performance of quicksort depends on the pivot chosen. E.g. if you always choose the first element as pivot, and you call quicksort with an already sorted array, quicksort will still try to sort it, because it doesn’t check if the array is already sorted.

If you use the first element as pivot, you are not splitting the array in 2 halves - one of the sub-arrays will always be empty. So the call stack will be long.

But if you always pick the middle element as the pivot, the call stack will be way shorter - there will be less recursive calls. Then, you reach the base case sooner.

You can consistently get the best case scenario, if you always choose a random element as the pivot.

Quicksort is one of the fastest sorting algorithms, and an example of divide-and-conquer.