Insertion Sort

Problem

Sort a list of integers in ascending order and return the sorted list.

Implement insertion sort: grow a sorted prefix one element at a time, shifting larger elements right until the new element finds its place. Return a new list and handle empty input and duplicates.

Hint

Shift elements greater than the key to the right, then drop the key into the gap.

Test cases

case 1

in: [[12,11,13,5,6]]

expected: [5,6,11,12,13]

case 2

in: [[]]

expected: []

case 3

in: [[1,2,3]]

expected: [1,2,3]

case 4

in: [[0,-2,8,-2]]

expected: [-2,-2,0,8]

Starter codePython

def insertion_sort(arr):
    # Your code here
    pass

4 test cases · run your code against them in the editor