Quick Sort

Quick sort

Quick sort is the fastest-known, comparison-based sorting algorithm for lists in the average case.

Note: Here’s a caveat; merge sort works better on linked lists and there are other non-comparison-based algorithms that outperform quick sort.

Steps for quick sort algorithm:

1. Start with a list of $n$ elements.
2. Choose a pivot element from the list to be sorted.
3. Partition the list into two unsorted sublists, such that all elements in one sublist are less than the pivot and all the elements in the other sublist are greater than the pivot.
4. Elements that are equal to the pivot can go in either sublist.
5. Sort each sublist recursively to yield two sorted sublists.
6. Concatenate the two sorted sublists and the pivot to yield one sorted list.

How to pick the pivot?

There are two methods by which we can choose a pivot.

Choosing randomly

The pivot can be picked randomly from the given elements. The chances of the first element being picked at every recursive call with this strategy is, ...