Quick Sort

• Quicksort does all the sorting in place!
• That's why it has a good space complexity. All the space complexity is due to the callstack

Steps

• Divide and conquer!

• Uses a pivoting technique

• Elect a pivot (first element in the array)

• Partition!: all elements smaller than the pivot are moved to the left, all elements greater than the pivot are moved to the right
• Each divided part is called recursively
• Concatenate everything together (left + pivot + right)

Complexity

• Time
• $O(n^2)$
• $\Theta(n*log(n))$
• $\Omega(n*log(n))$
• Space
• $O(log(n))$

$O(n)$ due to the partitioning (left + pivot + right)

$O(log(n))$ is due to the recursive sorting of each half

The runtime complexity can be $O(n^2)$ when the pivot is not distributed well around the mid point. In this case the $O(log(n))$ portion turns into $O(n)$