Quicksort

Quicksort is also a Divide and Conquer algorithm, and it is quite similar to the Merge sort algorithm. The main idea is to pick some pivot and partition all elements around it: elements less or equal – to the left side, and greater or equal – to the right one, and then sort these subarrays. That's the main difference with Merge Sort algorithm where the pivot element was the middle one.

There are many ways to pick the pivot element: pick the last element, the first one, random, etc. Here is an example with last elements as pivot.

partition(array, left, right) function builds a partitioned array around a pivot element with Time Complexity O(N). It returns the right index of the pivot element in array[left:right] and modifies the array according to the pivot.

quickSort() is a recursive sorting function similar to mergeSort(). It divides an array according to the pivot and recursively sorts the halves.

Time Complexity: O(NlogN) in average, but O(N^2) in the worst case.

The good case is when each time your pivot moves to the middle of an array during partition(). Then, this algorithm works like Merge Sort, where Time Complexity is O(NlogN). On average, pivot parties array on two arrays of almost the same length and reach this Time Complexity.

But the worst case is when your pivot parties array in subarrays of lengths N-1 and 1 each time. It can happen, if your array is already sorted, for example. Then, algorithm does O(N^2) operations (O(N) partitions for O(N) subarrays).

Space complexity: O(1)