## Merge Sort (Python implementation)

Pseudocode:

merge_sort(L): if L contain only 1 element: return L #divide L into two parts LEFT = half left of L RIGHT = half right of L #recursive call for two parts LEFT = merge_sort(LEFT) RIGHT = merge_sort(RIGHT) #merge two part together result = merge(LEFT, RIGHT) return result merge(LEFT, RIGHT): result = empty list while LEFT and RIGHT contain more than one element: append the smallest element in LEFT or RIGHT into result remove it (reduce size of LEFT or RIGHT) #in case there are some elements left inside LEFT or RIGHT while LEFT contain more than one element: append the first element of LEFT into result remove it out of LEFT while RIGHT contain more than one lement: append the first eleemnt of RIGHT into result remove it out of RIGHT return result

Example: [4,2,3,5,1]

*LEFT = [4,2]

-left = 4

-right = 2

-merge = [2,4]

*RIGHT = [3,5,1]

-left = 3

-right = [5,1]

–left = 5

–rigt = 1

–merge = [1,5]

-merge = [1,3,5]

*merge([2,4], [1,3,5])

result: 1,2,3,4,5

Implementation: Python2.7

""" Stimulate merge sort algorithm @author: loctv @time: 05:33PM January 3, 2017 (+7) """ def merge_sort(data): """ Sort function, repeatedly divide a list of values in two part untill there is only one left """ if len(data) == 1: #base case, data contains only one value return data #divide data into two parts left_side = data[:len(data)//2] #left right_side = data[len(data)//2:] #and right left_side = merge_sort(left_side) #recursive call to left side right_side = merge_sort(right_side) #recursive call to right side sorted_data = merge(left_side, right_side) #merge two sides together return sorted_data # return sorted list def merge(left_side, right_side): """ Merge method of merge-sort algorithm """ result = [] while len(left_side) > 0 and len(right_side) > 0: #append the smallest value in to result if left_side[0] < right_side[0]: result.append(left_side[0]) del left_side[0] else: result.append(right_side[0]) del right_side[0] #append the remain values on either left or right side while len(left_side) > 0: result.append(left_side[0]) del left_side[0] while len(right_side) > 0: result.append(right_side[0]) del right_side[0] return result if __name__ == '__main__': DATA = [4, 2, 3, 5, 1] DATA = merge_sort(DATA) print DATA

Advertisements

## Using merge sort to solve ‘Counting Inversions Problem’ | loctv 7:54 pm

onJanuary 3, 2017 Permalink |[…] faster way is using merge sort. If you still haven’t know merge sort yet, please check out this. Using merge sort, we can simultaneously count the number of inversions and sort data. The […]