User Tools

Site Tools


python:merge_sort

Differences

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

Link to this comparison view

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.
 +
 +<code python>
 +#​!/​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)))
 +</​code>​
 +
 +
 +See also [[python:​insertion_sort|insertion sort.]]
python/merge_sort.txt ยท Last modified: 2013/03/16 17:41 (external edit)