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