Last active
October 7, 2017 22:29
-
-
Save teschmitt/f3a47cc7e031ba29bff45a9ec480f569 to your computer and use it in GitHub Desktop.
A pythonic merge sort implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" 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