User Tools

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)))

See also insertion sort.

python/merge_sort.txt · Last modified: 2013/03/16 17:41 (external edit)