Common Mistakes in Quick Sort Implementation and How to Avoid Them

Quick Sort is a popular and often very fast sorting algorithm. It’s known for its efficiency in sorting large lists by cleverly dividing the problem into smaller pieces. However, because it involves recursion and careful array manipulation (partitioning), it’s easy to make small mistakes during implementation that can lead to incorrect results or even program crashes.

This article is designed for beginners who are learning about Quick Sort. We’ll look at some of the most common pitfalls you might encounter when writing Quick Sort code and provide simple, clear explanations on how to avoid them. Don’t worry if you’ve made these mistakes – they are part of the learning process! By the end, you’ll be more confident in implementing Quick Sort correctly.

Incorrect Base Case for Recursion

Quick Sort uses recursion, which means the function calls itself to solve smaller versions of the problem. A crucial part of any recursive function is the base case – the condition that tells the function when to stop calling itself.

Mistake: Forgetting the base case or getting the condition wrong.

# Incorrect: Missing or wrong base case
def quick_sort_wrong_base_case(arr, low, high):
  # Missing the if low < high check, or using something like if low >= high: return
  # This leads to infinite recursion if not careful
  pi = partition(arr, low, high)
  quick_sort_wrong_base_case(arr, low, pi - 1)
  quick_sort_wrong_base_case(arr, pi + 1, high)

Why It’s Wrong: If the function doesn’t know when to stop, it will keep calling itself indefinitely (or until the computer runs out of memory for function calls, causing a “stack overflow” error). Quick Sort should stop trying to sort a portion of the array when that portion has zero or one element, as such arrays are already sorted by definition.

Fix: Always include a check at the beginning of your quickSort function to see if the low index is still less than the high index. If low is greater than or equal to high, it means the current segment has 0 or 1 element, and you should simply return (do nothing).

def quick_sort_correct_base_case(arr, low, high):
  # Correct Base Case: Only proceed if there's more than one element
  if low < high:
    pi = partition(arr, low, high)
    quick_sort_correct_base_case(arr, low, pi - 1)
    quick_sort_correct_base_case(arr, pi + 1, high)
  # If low >= high, the function implicitly returns (does nothing), stopping recursion.

Off-by-One Errors in Partitioning Loops

The partition function is the core of Quick Sort. It rearranges elements around a pivot. This involves carefully managing array indices. Making small “off-by-one” errors in loop boundaries or indices is very common.

Let’s consider the Lomuto partition scheme (often uses the last element as pivot) for illustration.

Mistake: Incorrect loop bounds or using the wrong index when swapping.

# Incorrect Partitioning Loop (Example using Lomuto idea)
def partition_wrong_loop(arr, low, high):
  pivot = arr[high]
  i = low - 1
  # Loop goes one step too far, or uses wrong index
  for j in range(low, high + 1): # Incorrect: Should be range(low, high)
    if arr[j] <= pivot:
      i = i + 1
      # Potentially swapping with wrong indices if loop is wrong
      arr[i], arr[j] = arr[j], arr[i]

  # Final swap might also use wrong index if 'i' is calculated incorrectly
  # arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1 # Return value might be wrong

Why It’s Wrong:

Looping too far (e.g., including the pivot index high in the main comparison loop) can lead to incorrect comparisons or swapping the pivot prematurely.
Using the wrong index for i (the boundary for smaller elements) or j (the scanner) can mess up the partitioning logic.
This results in elements not being placed correctly relative to the pivot, leading to an incorrectly sorted final array.

Fix: Be precise with loop ranges and indices. In Lomuto partitioning (with the last element as pivot):

The main loop should typically go from low up to high - 1.
The index i should track the position where the next smaller element should go.
Ensure the final swap places the pivot at the correct position, which is usually i + 1.

# Correct Partitioning Loop (Lomuto example)
def partition_correct_loop(arr, low, high):
  pivot = arr[high]
  i = low - 1 # i is the index of the last element known to be <= pivot

  # Loop correctly from low up to (but not including) high
  for j in range(low, high):
    if arr[j] <= pivot:
      i = i + 1
      arr[i], arr[j] = arr[j], arr[i] # Swap current element into the 'less than' partition

  # Swap pivot into its final correct place
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1 # Return the pivot's final index

Incorrect Recursive Call Boundaries

After partitioning, the pivot is in its final correct place. The next step is to recursively sort the two sub-arrays: the one before the pivot and the one after the pivot. A common mistake is including the pivot itself in these recursive calls.

Mistake: Passing the wrong indices to the recursive quickSort calls.

# Incorrect Recursive Calls
def quick_sort_wrong_recursion(arr, low, high):
  if low < high:
    pi = partition(arr, low, high) # pi is the pivot's final index

    # Incorrect: Includes the pivot 'pi' in the recursive call
    quick_sort_wrong_recursion(arr, low, pi)
    # Incorrect: Includes the pivot 'pi' again
    quick_sort_wrong_recursion(arr, pi, high)

Why It’s Wrong:

Including the pivot index (pi) in the recursive calls is unnecessary because the pivot is already in its final sorted position after partitioning.
Worse, if the partition function doesn’t handle this perfectly (e.g., if pi ends up being low or high), including the pivot can lead to infinite recursion, as you might repeatedly try to sort a sub-array that isn’t getting smaller.

Fix: Ensure the recursive calls operate on the ranges strictly before and strictly after the pivot’s final index (pi).

# Correct Recursive Calls
def quick_sort_correct_recursion(arr, low, high):
  if low < high:
    pi = partition(arr, low, high) # pi is the pivot's final index

    # Correct: Sort the sub-array BEFORE the pivot (low to pi-1)
    quick_sort_correct_recursion(arr, low, pi - 1)

    # Correct: Sort the sub-array AFTER the pivot (pi+1 to high)
    quick_sort_correct_recursion(arr, pi + 1, high)

Mishandling Pivot Placement After Partitioning

Even if the partitioning loop is correct, the final step of placing the pivot into its correct position must be done accurately.

Mistake: Swapping the pivot with the wrong element at the end of the partition function.

# Incorrect Final Pivot Swap (Lomuto example)
def partition_wrong_final_swap(arr, low, high):
  pivot = arr[high]
  i = low - 1
  for j in range(low, high):
    if arr[j] <= pivot:
      i = i + 1
      arr[i], arr[j] = arr[j], arr[i]

  # Incorrect: Swapping pivot with arr[i] instead of arr[i+1]
  arr[i], arr[high] = arr[high], arr[i]
  return i # Returning the wrong index too

Why It’s Wrong: After the loop, i points to the last element that was found to be less than or equal to the pivot. The correct spot for the pivot is the next position, i + 1, which is the beginning of the “greater than pivot” section. Swapping with arr[i] puts the pivot one position too early.

Fix: Always swap the pivot element (which was initially moved to arr[high] in this Lomuto example) with the element at index i + 1.

# Correct Final Pivot Swap (Lomuto example)
def partition_correct_final_swap(arr, low, high):
  pivot = arr[high]
  i = low - 1
  for j in range(low, high):
    if arr[j] <= pivot:
      i = i + 1
      arr[i], arr[j] = arr[j], arr[i]

  # Correct: Swap pivot with the element at index i+1
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  return i + 1 # Return the correct final pivot index

Recap of Key Takeaways

Avoiding these common mistakes will help you write a correct Quick Sort implementation:

Implement the Base Case: Always check if low < high to stop recursion correctly.
Manage Partition Indices Carefully: Ensure loop boundaries (low to high-1 typically) and swapping indices (i and j) are accurate in the partition function.
Place the Pivot Correctly: After partitioning, swap the pivot into its final position (usually i + 1).
Make Correct Recursive Calls: Exclude the pivot’s final index (pi) from the recursive calls: use quickSort(arr, low, pi - 1) and quickSort(arr, pi + 1, high).

Practice and careful testing are key! Stepping through your code with a small example array can often reveal these types of errors.

What’s Next?

Now that you’re aware of common Quick Sort implementation mistakes, you might want to learn more about: