# Goodies Lemonsoftare

### Site Tools

python:merge_sort

# Differences

This shows you the differences between two versions of the page.

 — python:merge_sort [2013/03/16 17:41] (current) Line 1: Line 1: + ==== MERGESORT ==== + 31.08.2012 + + As from [[http://​en.wikipedia.org/​wiki/​Merge_sort | wikipedia]]:​ + + Merge sort (also commonly spelled mergesort) is an //O(n log n)// comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. + + + #​!/​usr/​bin/​env python + # + # MERGESORT + # + # divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). + # compare each element with the adjacent list to sort and merge the two adjacent lists. ​ + # + + def run_mergesort(unsorted_list):​ + return merge_split(unsorted_list) + + + def merge_split(ulist):​ + elements = len(ulist) + + # recursive function + if elements > 1: + middle = elements/2 + ​ + left = merge_split(ulist[:​middle]) + right = merge_split(ulist[middle:​]) + + return merge(left, right) + return ulist + + + def merge(left, right): + result = [] + left_elements = len(left) + right_elements = len(right) + i = j = 0 + + while i < left_elements and j < right_elements:​ + if left[i] <= right[j]: + result.append(left[i]) + i += 1 + else: + result.append(right[j]) + j += 1 + + result.extend(left[i:​]) + result.extend(right[j:​]) + + return result + ​ + + if __name__ == '​__main__':​ + entered_str_numbers = raw_input("​Row with separated numbers by space (ENTER to finish): ") + list_numbers = entered_str_numbers.split("​ ") + ​ + try: + clean_list_numbers = [] + for d in list_numbers:​ + clean_list_numbers.append(int(d)) + except ValueError: + pass + ​ + sorted_list_numbers = run_mergesort(clean_list_numbers) + ​ + print "​Unsorted:​ {0}"​.format("​ "​.join(map(str,​ clean_list_numbers))) ​   ​ + print "​Sorted:​ {0}"​.format("​ "​.join(map(str,​ sorted_list_numbers))) + ​ + + + See also [[python:​insertion_sort|insertion sort.]]