[PYTHON] Merge sort using recursion

How to merge sort using recursion

• It feels like a memorandum (because I forget it when I look back, I think there are things that I can not understand with just the code)

Array data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]

1. Divide into left and right in the middle of the array => Left [3,1,9,4,2] Right [5,7,6,8,10] Middle: 5

2. Divide further by left and right (using recursion) => Left [3,1,9,4,2]-> Left [3,1] Right [9,4,2] Middle: 2 Right [5,7,6,8,10]-> Left [5,7] Right [6,8,10] ....

3. Finally, it will be [3], [1], [9], [4], [2], [5], [7], [6], [8], [10](preparation completed) !)

4. This time, the values divided into two are sorted in order from the left (because it starts from 0), and the sort result is assigned to result_sort (combination). [3,1], [4,2] => Each Sort [1,3] [2,4]

• There are no [9] and [6]! why? => When dividing [9,4,2] Since the center is "1", right: [9] Left: [4,2], so processing starts from [4,2] first. (For recursion, proceed as 1-> 2-> 3-> 4-> 5, and then rewind while rewinding as 5-> 4-> 3-> 2-> 1) => * * To deepen your understanding, study recursion **

5. [9] and [4,2] are sorted by-> [9] and [4,2]-> result_sort => [2,4,9]
6. [3,1] and [9,4,2] are sorted by-> [3,1] and [9,4,2]-> result_sort => [1,2,3,4,9]
7. Right is complete. Next, do 4 to 6 from the left 8 [3,1,9,4,2] and right [5,7,6,8,10] are compared 9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Explanation in code (python)

sample.py

data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]

Assign data to a variable

sample.py

def merge_sort(data):
    if len(data) <= 1: #True if the contents of the array are 1 or less
        return data
    center = len(data) // 2 #Center of array
    left = merge_sort(data[:center])#Divided to the left[3,1,9,4,2] => [3,1] => [3]
    right = merge_sort(data[center:]) #Divided to the right[5,7,6,8,10] => [9,4,2] => [1]
    return left, right #=> [3], [1]Is passed

You can do 1 ~ 3 with this code.

sample.py

def merge_sort(data):
    if len(data) <= 1: #True if the contents of the array are 1 or less
        return data
    center = len(data) // 2 #Center of array
    left = merge_sort(data[:center])#Divided to the left[3,1,9,4,2] => [3,1] => [3]
    right = merge_sort(data[center:]) #Divided to the right[5,7,6,8,10] => [9,4,2] => [1]
    return merge(left, right)

Just add return merge (left, right)

sample.py

def merge(left, right):
    result_sort = [] #Combined result
    left_i, right_j = 0, 0
    print(left + right) #=>You can see the array you are trying to sort
    while(left_i < len(left)) and (right_j < len(right)):
        if left[left_i] <= right[right_j]:
            result_sort.append(left[left_i]) #Here, compare the right and left you are trying to combine and hit the result.
            left_i += 1
        else:
            result_sort.append(right[right_j]) #Here, compare the right and left you are trying to combine and hit the result.
            right_j += 1
    if len(left[left_i:]) != 0: #=>True if the number in the left array that has been sorted but left over is not 0(left_Check with i)
        result_sort.extend(left[left_i:])
    if len(right[right_j:]) != 0:
        result_sort.extend(right[right_j:]) #True (right) if the number in the array of right that has been sorted but is left over is not 0_Confirm with j)
    print(result_sort) #=>You can see the sorted array
    return result #Final return value

Doing 4 ~ 8

Quote (Thank you)

• https://medium-company.com/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88/
• https://qiita.com/woolon/items/4cff50de7e697cb2664f