Implementation

Let’s code quick sort. It’s elegant with recursion.

Complete Implementation

              function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
  const pi = partition(arr, low, high);
  quickSort(arr, low, pi - 1);
  quickSort(arr, pi + 1, high);
}
return arr;
}

function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;

for (let j = low; j < high; j++) {
  if (arr[j] < pivot) {
    i++;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
            

              def quick_sort(arr, low=0, high=None):
  if high is None:
      high = len(arr) - 1
  
  if low < high:
      pi = partition(arr, low, high)
      quick_sort(arr, low, pi - 1)
      quick_sort(arr, pi + 1, high)
  
  return arr

def partition(arr, low, high):
  pivot = arr[high]
  i = low - 1
  
  for j in range(low, high):
      if arr[j] < pivot:
          i += 1
          arr[i], arr[j] = arr[j], arr[i]
  
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1
            

Try It Yourself

Code Explanation

1. Base case: If low >= high, sub-array is sorted
2. Partition: Rearrange around pivot, get pivot index
3. Recurse: Sort left and right sub-arrays
4. In-place: Modifies original array

Edge Cases

• Empty array: Returns as-is (base case)
• Single element: Returns as-is (base case)
• Already sorted: Still partitions (but efficiently)

Optimizations

1. Random pivot: Reduces worst-case probability
2. Median of three: Better pivot selection
3. Insertion sort for small arrays: Switch to insertion sort for small sub-arrays
4. Iterative version: Avoid recursion overhead

What’s Next?

Now that you can implement it, let’s analyze its performance and complexity.