Insertion Sort

Implement the classic insertion sort algorithm with in-place mutation.

sorting in-place algorithms

Write a function `insertion_sort(arr)` that sorts a list of integers in ascending order using the insertion sort algorithm. The function must mutate the input list in-place and return the same list object. Do not use built-in sorting functions like `sorted()` or `list.sort()`. The algorithm should work for lists of any length, including empty lists.

Constraints

0 <= len(arr) <= 10^4. Elements are integers. The sort must be stable (not required to prove, but the algorithm naturally is).

Example

>>> arr = [5, 2, 9, 1]
>>> result = insertion_sort(arr)
>>> result is arr
True
>>> result
[1, 2, 5, 9]

>>> lst = []
>>> insertion_sort(lst)
[]

>>> lst = [3]
>>> insertion_sort(lst)
[3]

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start from the second element and treat the left side as the sorted portion.

Shift elements to the right until you find the correct position for the current key.

Don't create a new list; modify the input list directly.

The function should end with `return arr`.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.