Quick Sort

Quick Sort

Quick Sort is the most widely used sorting algorithm in practice. Like merge sort, it uses divide and conquer. It picks a pivot element and partitions the array so that all elements smaller than the pivot come before it, and all larger elements come after.

How It Works

1. If the array has 0 or 1 element, return it (base case).
2. Pick a pivot (commonly the last element).
3. Partition: collect elements ≤ pivot into left, elements > pivot into right.
4. Recursively sort left and right.
5. Return [...quickSort(left), pivot, ...quickSort(right)].

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = arr.slice(0, -1).filter(x => x <= pivot);
  const right = arr.slice(0, -1).filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

Complexity

Quick sort is in-place in its classic implementation (using index-based partitioning instead of creating new arrays). It is typically faster than merge sort in practice due to better cache performance. C's qsort and C++'s std::sort are based on quicksort variants.

Your Task

Implement quickSort(arr) that returns a new sorted array. Use the last element as the pivot.