Instantly share code, notes, and snippets.

# lfreeman/merge_sort.py Created Dec 3, 2012

What would you like to do?
Merge Sort
 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()