public
Created

Merge Sort

  • Download Gist
merge_sort.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
import numpy.random as nprnd
import time
 
 
def timeit(method):
def timed(*args, **kwargs):
ts = time.time()
result = method(*args, **kwargs)
te = time.time()
print '%s (%s) %2.2f sec' % \
(method.__name__, len(args[0]), te - ts)
return result
return timed
 
 
@timeit
def merge_sort(list,merge):
return _merge_sort(list, merge)
 
def merge1(left, right):
i = j = inv = 0
merged = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
inv += len(left[i:])
 
merged += left[i:]
merged += right[j:]
return merged, inv
 
def merge2(array1, array2):
inv = 0
merged_array = []
while array1 or array2:
if not array1:
merged_array.append(array2.pop())
elif (not array2) or array1[-1] > array2[-1]:
merged_array.append(array1.pop())
inv += len(array2)
else:
merged_array.append(array2.pop())
merged_array.reverse()
return merged_array, inv
 
def _merge_sort(list, merge):
len_list = len(list)
if len_list < 2:
return list, 0
middle = len_list / 2
left, left_inv = _merge_sort(list[:middle], merge)
right, right_inv = _merge_sort(list[middle:], merge)
l, merge_inv = merge(left, right)
inv = left_inv + right_inv + merge_inv
return l, inv
 
def main():
test_list = nprnd.randint(1000, size=50000).tolist()
 
test_list_tmp = list(test_list)
merge_sort(test_list_tmp, merge1)
 
test_list_tmp = list(test_list)
merge_sort(test_list_tmp, merge2)
 
if __name__ == '__main__':
main()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.