Quick Sort is the standard "in-place" sorting algorithm used by most programming languages in their sort() functions. It uses a Pivot to partition the array into smaller and larger elements.

Think of a Classroom of Students standing in a random line:

1. You pick one student (The Pivot).
2. You tell everyone: "If you are shorter than the pivot, go to the left. If you are taller, go to the right."
3. Now, the Pivot student is standing in their exactly correct spot in the sorted line.
4. Now, the students to the left and right repeat the same process among themselves.
5. Soon, every student is in their correct spot.

---

Complexity Analysis

• Best/Avg Time: $O(n \log n)$. This happens when the pivot consistently divides the array into roughly equal halves.
• Worst Time: $O(n^2)$. This happens if the array is already sorted and you always pick the smallest or largest element as the pivot. (Modern implementations use Randomized Pivots to avoid this).
• Space: $O(\log n)$ for the recursion stack.

Key Characteristics

• In-Place: It sorts the original array and doesn't need $O(n)$ extra memory (Unlike Merge Sort).
• Unstable: It does NOT preserve the original order of equal elements.

---

javascript Standard
/**
 * Quick Sort Entry
 */
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex); // Sort Left
    quickSort(arr, pivotIndex + 1, high); // Sort Right
  }
  return arr;
}

/**
 * Hoare Partition Scheme
 */
function partition(arr, low, high) {
  const pivot = arr[Math.floor((low + high) / 2)];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j;
    
    // Swap
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

---

How to avoid O(n²)?

Interviewers will ask: "What if the input is sorted?" Answer: Use a randomized pivot or "median-of-three" pivot selection to make the $O(n^2)$ case virtually impossible.

Common Questions

• Why is Quick Sort preferred over Merge Sort for arrays? (Answer: Better locality of reference and less memory overhead).
• Is Quick Sort stable? Why or why not?
• Explain the difference between Hoare and Lomuto partitioning schemes.