The basic idea

Merges two or more ordered subsequences into an ordered sequence. In internal sort, 2- way merge sort is usually used.

  • The numbers to be sorted in the sequence are divided into several groups, with each number divided into one group
  • Combine several groups in pairs to ensure that the combined group is orderly
  • Repeat step 2 until only one group is left and the sorting is complete

Merging two sequences

Now we have two ordered subsequences, and the next thing to do is combine the two sequences

First, set a pointer in two ordered subsequences respectively, and then select elements from the ordered subsequence by moving the pointer for comparison and then put them into an empty sequence

Compare numbers in subsequences, for example 17 is greater than 4, add 4 to the following sequence, and move the 4-position pointer one position forward (to the right). The position of the pointer in the right sequence is 9, and then the value of 17 is still 17 when 9 and 17 are compared. Therefore, 9 is placed in the following sequence and the position of the pointer on the right is greater than 17. After 17 is placed in the following sequence, the left pointer is moved one position forward

By repeating the above steps until one of the Pointers reaches the last element of an ordered array and is placed in the following array, if another ordered subsequence has any remaining elements, since the remaining children are already ordered, it can be moved into the sequence as well.

As can be seen from the above figure, the whole sorting is also divided first and then the sub-sequence is sorted.

The first is the partitioning process that divides the array in pairs until each subsequence has only one element

These elements are then combined to form the original sequence, and the merging process adjusts it to an ordered sequence

Code implementation

How to combine two ordered subsequences into a sequence, and the sequence is still ordered after combination

def merge_two_sorted_lists(a,b) :
    sorted_list = []

    return sorted_list

if __name__ == '__main__':
    a = [5.8.12.56]
    b = [7.9.45.51]

    print(merge_two_sorted_lists(a,b))
Copy the code
def merge_two_sorted_lists(a,b) :
    sorted_list = []
    len_a = len(a)
    len_b = len(b)

    i = j = 0

    while i < len_a and j < len_b:
        if a[i] <= b[j]:
            sorted_list.append(a[i])
            i += 1
        else:
            sorted_list.append(b[j])
            j += 1
    while i < len_a:
        sorted_list.append(a[i])
        i += 1
    while j < len_b:
        sorted_list.append(b[j])
        j += 1

    return sorted_list

if __name__ == '__main__':
    a = [5.8.12.56]
    b = [7.9.45.51]

    print(merge_two_sorted_lists(a,b))
Copy the code

The above code is somewhat readable. The method takes two ordered sequences a and b as arguments, passing I < len_a and j < len_b

The diagram above explains that when j = 4 the loop cannot be entered, so 56 cannot be placed in the sequence. So the following code prevents the last element from being placed into the sequence

    while i < len_a:
        sorted_list.append(a[i])
        i += 1
    while j < len_b:
        sorted_list.append(b[j])
        j += 1
Copy the code

Divide the sequence

def merge_sort(arr) :
    if len(arr) <= 1:
        return arr
    
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge_two_sorted_lists(left,right)
Copy the code

I’m going to use recursion here

def merge_sort(arr) :
    if len(arr) <= 1:
        return arr
    
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge_two_sorted_lists(left,right)

def merge_two_sorted_lists(a,b) :
    sorted_list = []
    len_a = len(a)
    len_b = len(b)

    i = j = 0

    while i < len_a and j < len_b:
        if a[i] <= b[j]:
            sorted_list.append(a[i])
            i += 1
        else:
            sorted_list.append(b[j])
            j += 1
    while i < len_a:
        sorted_list.append(a[i])
        i += 1
    while j < len_b:
        sorted_list.append(b[j])
        j += 1

    return sorted_list

if __name__ == '__main__':
    a = [5.8.12.56]
    b = [7.9.45.51]

    arr = [5.8.12.56.7.9.45.51]

    print(merge_sort(arr))
Copy the code

The code above, however, opens up new space for merging ordered subsequences, and we want to not open up new space for placing ordered elements on the original array.

def merge_sort(arr) :
    if len(arr) <= 1:
        return arr
    
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]

    # left = merge_sort(left)
    # right = merge_sort(right)
    merge_sort(left)
    merge_sort(right)

    return merge_two_sorted_lists(left,right,arr)



def merge_two_sorted_lists(a,b,arr) :
    # sorted_list = []
    len_a = len(a)
    len_b = len(b)

    i = j = k = 0

    while i < len_a and j < len_b:
        if a[i] <= b[j]:
            arr[k] = a[i]
            # sorted_list.append(a[i])
            i += 1
        else:
            arr[k] = b[j]
            # sorted_list.append(b[j])
            j += 1
        k+=1
    while i < len_a:
        # sorted_list.append(a[i])
        arr[k] = a[i]
        i += 1
        k += 1
    while j < len_b:
        arr[k] = b[j]
        # sorted_list.append(b[j])
        j += 1
        k += 1

    # return sorted_list

if __name__ == '__main__':
    a = [5.8.12.56]
    b = [7.9.45.51]

    arr = [5.8.12.56.7.9.45.51]
    merge_sort(arr)
    print(arr)
Copy the code