Skip to content

Instantly share code, notes, and snippets.

@teschmitt
Last active October 7, 2017 22:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save teschmitt/f3a47cc7e031ba29bff45a9ec480f569 to your computer and use it in GitHub Desktop.
Save teschmitt/f3a47cc7e031ba29bff45a9ec480f569 to your computer and use it in GitHub Desktop.
A pythonic merge sort implementation
""" Straightforward approach, shaving sorted elements off of the beginning of the partitions """
def merge(l_left, l_right):
l_sorted = []
while l_left and l_right:
if l_left[0] <= l_right[0]:
l_sorted.append(l_left.pop(0))
else:
l_sorted.append(l_right.pop(0))
# Extend return variable by list with remaining entries
return l_sorted + l_left + l_right
""" Build sorted partitions in reverse to avoid having to pop(0) and decrease runtime """
def merge_rev(l_left, l_right):
l_sorted = []
while l_left and l_right:
if l_left[-1] >= l_right[-1]:
l_sorted.append(l_left.pop())
else:
l_sorted.append(l_right.pop())
l_sorted.reverse()
return l_left + l_right + l_sorted
def merge_sort(l, merge_f):
len_l = len(l)
if len_l <= 1: return l
mid = len_l//2
return merge_f(merge_sort(l[:mid], merge_f), merge_sort(l[mid:], merge_f))
import random
li = random.sample(range(50000), 50000)
print('merge ', end=' ')
%timeit merge_sort(li, merge)
print('merge_rev', end=' ')
%timeit merge_sort(li, merge_rev)
print('Timsort ', end=' ')
%timeit sorted(li))
"""
OUTPUT: ----------------------------------------------------------------------
merge 634 ms ± 6.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
merge_rev 306 ms ± 1.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Timsort 16.6 ms ± 351 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment