Like merge sort, quick sort also sorts using the principle of divide and conquer—It also takes O(n log n) to do its job, but in the extreme worst case, it can take O(n2) to sort n elements (which is very rare). We can do this in place, so the memory used in quick sort is less.
Understanding quick sort
How the quick sort algorithm works
The following gives a brief idea about how quick sort works:
- It chooses an element called the pivot element
- It divides the input collection into two sub-collections based on the pivot element
- The division happens in a way that all elements in the left sub-collection are smaller than the pivot element, and all elements in the right sub-collection are larger than the pivot element
- Now...