Quick sort is really very confusing and the following implementation is merely one in many. Originally I wanted to write about quicksort from scratch but it dawned upon me that textual discussion simply cannot transcend the idea easily. Hence, I linked a Youtube video here to let you have a visual understanding. This seems to be best video online which uses in-place O(1) space complexity. The video explains the concept of using the last element as pivot and then recursively splits the array down till the base case of 1 element. I am impressed by this video because it tracks the recursion step by step, giving beginners a crystal clear explanation.
Below is my python implementation based on the video’s concept.
The time complexity of this implementation of quicksort depends. In the worst case, whereby the initial array passed in is already sorted, the efficiency will be O(n²). This is because the pivot has to compare every single element in the array, similar to how bubblesort works. However, in average and best case, the efficiency will be O(nlogn). You can show this by simply making a table to see how number of comparison vs size of array grows.
There are other implementations out there which uses auxiliary arrays for quicksort, but that is usually not the case in textbooks. Other optimization of quicksort could include using a random element as pivot each time so as to not go into the worst case scenario.
Happy coding!
