A little late the the party, but I figured I'd throw my hat in the ring as my solution seems to run faster than OP's (on my machine, anyway):
# [Python 3]
def merge_sort(arr):
if len(arr) < 2:
return arr
half = len(arr) // 2
left = merge_sort(arr[:half])
right = merge_sort(arr[half:])
out = []
li = ri = 0 # index of next element from left, right halves
while True:
if li >= len(left): # left half is exhausted
out.extend(right[ri:])
break
if ri >= len(right): # right half is exhausted
out.extend(left[li:])
break
if left[li] < right[ri]:
out.append(left[li])
li += 1
else:
out.append(right[ri])
ri += 1
return out
This doesn't have any slow pop()s, and once one of the half-arrays is exhausted, it immediately extends the other one onto the output array rather than starting a new loop.
I know it's machine dependent, but for 100,000 random elements (above merge_sort() vs. Python built-in sorted()):
merge sort: 1.03605 seconds
Python sort: 0.045 seconds
Ratio merge / Python sort: 23.0229