# -*- coding: utf-8 -*- """ Demo of the merge sort, studied last week in the lectures (CS101 lecture week 9). - This program is also available on Moodle ! - One graphical representation of an execution can be seen at https://en.wikipedia.org/wiki/File:Merge-sort-example-300px.gif - More details on https://en.wikipedia.org/wiki/Merge_sort @date: Sat Mar 7 18:07:23 2015. @author: Arya K. Bhattacharya for CS101 course at Mahindra Ecole Centrale 2015. """ def merge(left, right): """ Assumes left and right are sorted lists. Puts them together in a new sorted list result which is returned. """ result = [] i = 0 j = 0 # Going over a condition-based dual loop over both # 'left' and 'right' while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # end if-else construction # end while loop # It is unlikely that both 'right' and 'left' have reached # their max values simultaneously. Hence, below code # completes the remaining values. while i < len(left): result.append(left[i]) i += 1 while j < len(right): result.append(right[j]) j += 1 return result # end of function def merge_sort(s, k=-1): """ Sort the list s with the merge sort (recursive) algorithm. k is just used for showing the calls that are left or right.""" print "In merge_sort, k=", k, "for a list of size", len(s), ":", s if len(s) < 2: return s[:] # new copy of the list! else: mid = len(s)/2 # integer division, rounded below left = merge_sort(s[0:mid], k=0) # first left half right = merge_sort(s[mid:], k=1) # second right half combine = merge(left, right) print "In merge_sort, I merged left and right to have a list of size", len(combine), ":", combine return combine # end of if-else condition # end of function s = [3.2, 8.6, 42.7, 21.5, 17.0, 11.9, 11.88, 13.75, 89.7, 65.4, 33.7] print "With an example of non-sorted list:" print s print "In call, from argument ", s sorted_s = merge_sort(s) print "In call, from returned ", sorted_s