Time and Space Complexity

Time Complexity:

• Average Case: O(n log n)
  • A balanced pivot splits the array roughly in half each time, giving about log n levels of O(n) partitioning work.
• Worst Case: O(n²)
  • If the pivot is always the smallest or largest element (for example, an already sorted array with the last element as pivot), one side is empty every time and the recursion becomes n levels deep.

Space Complexity:

• O(n) for the version we build here, since we create new smaller and larger lists at each step. The classic in-place Quick Sort improves this to O(log n) extra space.

Summary:

• Quick Sort is very fast on average and is a go-to sorting algorithm in practice.
• A poor pivot choice can degrade it to O(n²); good pivot strategies (like choosing a random or median element) avoid this.