Merge Sort

Problem

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

Recursively split the list in half, sort each half, then merge the two sorted halves by repeatedly taking the smaller front element. Return a new list and handle empty input.

Hint

Split, recurse, then merge with two pointers; take from the left half on ties for stability.

Test cases

case 1

in: [[38,27,43,3,9,82,10]]

expected: [3,9,10,27,38,43,82]

case 2

in: [[]]

expected: []

case 3

in: [[1]]

expected: [1]

case 4

in: [[5,4,3,2,1]]

expected: [1,2,3,4,5]

Starter codePython

def merge_sort(arr):
    # Your code here
    pass

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