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

```