Common Mistakes in Insertion Sort and How to Avoid Them

Insertion sort is a straightforward and intuitive sorting algorithm. However, even experienced programmers can make mistakes when implementing it. Whether you’re a beginner or someone brushing up on sorting algorithms, it’s easy to fall into common pitfalls. In this article, we’ll explore the most frequent mistakes made while implementing insertion sort and provide practical tips to avoid them. By the end, you’ll be able to write a bug-free insertion sort implementation with confidence!

Incorrect Loop Boundaries

One of the most common mistakes is getting the loop boundaries wrong. For example, starting the loop from the wrong index or using incorrect conditions can lead to incomplete sorting or even runtime errors.

Mistake:

for i in range(0, len(arr)):  # Starts from 0 instead of 1
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1
  arr[j + 1] = key

Why It’s Wrong:

  • Starting from i = 0 means the algorithm tries to compare arr[-1] with arr[0], which can cause an out-of-bounds error or unnecessary comparisons. Remember that in Python, accessing arr[-1] will return the last element of the array, which is likely not what we want in this case.

Fix:

Always start the loop from i = 1 because the first element is already considered sorted.

for i in range(1, len(arr)):  # Correct loop boundary
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1
  arr[j + 1] = key

Forgetting to Shift Elements

Another common mistake is forgetting to shift elements to make space for the key element. This can result in overwriting data or incorrect sorting.

Mistake:

for i in range(1, len(arr)):
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    j -= 1  # Forgot to shift elements
  arr[j + 1] = key

Why It’s Wrong:

  • Without shifting elements, the key is placed in the wrong position, and the array remains unsorted. The elements larger than key should be shifted to the right to create space for key.

Fix:

Always shift elements greater than the key to the right.

for i in range(1, len(arr)):
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]  # Shift elements
    j -= 1
  arr[j + 1] = key

Incorrect Placement of the Key

Placing the key in the wrong position is another frequent error. This usually happens when the index j is not updated correctly.

Mistake:

for i in range(1, len(arr)):
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1
  arr[j] = key  # Wrong placement

Why It’s Wrong:

  • The key is placed at arr[j] instead of arr[j + 1], which can lead to incorrect sorting. After the while loop, j will be the index of the element just smaller than key (or -1 if key is the smallest so far), so we need to insert key at j + 1.

Fix:

Always place the key at arr[j + 1] after shifting elements.

for i in range(1, len(arr)):
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1
  arr[j + 1] = key  # Correct placement

Ignoring Edge Cases

Failing to handle edge cases, such as an empty array or an array with a single element, can lead to unexpected behavior.

Mistake:

def insertion_sort(arr):
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key
  return arr

Why It’s Wrong:

  • If the array is empty or has only one element, the function still tries to run the loop, which is unnecessary. While it won’t cause an error, it’s more efficient to handle these cases directly.

Fix:

Add a check for edge cases at the beginning of the function.

def insertion_sort(arr):
  if len(arr) <= 1:  # Handle edge cases
    return arr
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key
  return arr

Not Preserving Stability

Insertion sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. However, incorrect implementation can break this property.

Mistake:

for i in range(1, len(arr)):
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] >= key:  # Using >= instead of >
    arr[j + 1] = arr[j]
    j -= 1
  arr[j + 1] = key

Why It’s Wrong:

  • Using >= instead of > can change the order of equal elements, making the algorithm unstable. If arr[j] is equal to key, shifting arr[j] to the right will put key after arr[j] even though they were in the opposite order originally.

Fix:

Use > to compare elements and preserve stability.

for i in range(1, len(arr)):
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:  # Correct comparison
    arr[j + 1] = arr[j]
    j -= 1
  arr[j + 1] = key

Recap of Key Takeaways

  1. Start the loop from i = 1: The first element is already sorted.
  2. Shift elements correctly: Always shift elements greater than the key to the right.
  3. Place the key at arr[j + 1]: Ensure the key is inserted in the correct position.
  4. Handle edge cases: Check for empty arrays or arrays with a single element.
  5. Preserve stability: Use > instead of >= to maintain the relative order of equal elements.

By avoiding these common mistakes, you can implement insertion sort correctly and efficiently.

What’s Next?

Now that you understand common mistakes in insertion sort implementation, you might want to explore: