# Goodies Lemonsoftare

### Site Tools

python:merge_sort

### MERGESORT

31.08.2012

As from 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)))``` 