Detailed introduction to the implementation steps of the merge sort algorithm in Python programming

Basic idea: Merge sort is a typical divide-and-conquer idea, which divides an unordered list into two, and then divides each subsequence into two, and continues until it can no longer be divided. Then, the merging process begins, comparing the elements of each subsequence with another subsequence, and sequentially putting the small elements into the result sequence for merging, and finally completing the merge sorting.

Merge operation process:

Apply for space so that its size is the sum of two sorted sequences. This space is used to store the merged sequence
Set two pointers, the initial positions are the starting positions of the two sorted sequences respectively
Compare the elements pointed to by the two pointers, select the relatively small element and put it into the merge space, and move the pointer to the next Position
Repeat step 3 until a certain pointer reaches the end of the sequence
Copy all the remaining elements of the other sequence directly to the end of the merged sequence
The above statement is a theoretical statement. Here is a practical example to illustrate:

For example, an unordered array

[6,2,3,1,7]

First decompose the array recursively until:

[6],[2],[3],[1],[7]

Then start the merge sorting, also in a recursive way:

merge and sort two by two, get:

[2,6],[1,3],[7]

In the previous step, it was actually merged according to the method of this step, but because there is a number in each list, the process cannot be fully displayed. The process can be fully shown below.

Initial:

 a = [2,6] b = [1,3] c = []

Step 1, take out a number from a, b in sequence: 2, 1, compare the size and put it into c , and delete the number from the original list, the result is:

a = [2,6] b = [3] c = [1]

Step 2, continue to remove the numbers from a and b in order, also Just repeat the above steps, this time it is: 2,3, compare the size and put it into c, and delete the number from the original list. The result is:

a = [6] b = [3] c = [1,2]

Step 3, repeat the previous steps, the result is:

a = [6] b = [] c = [1,2,3]

The last step is to append 6 to c, the result is:

a = [] b = [] c = [1,2,3,6]

By repeatedly applying the above process, the merging of [1,2,3,6] and [7] is achieved

finally obtains the sorting result

[1,2,3,6,7]

This article lists three python implementation methods:

Method 1: Translate the process described above Here we go, a little clumsy first

#! /usr/bin/env python
#coding:utf-8

def merge_sort(seq):
 if len(seq) ==1:
 return seq
 else:
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])

 i = 0 #left 计数
 j = 0 #right 计数
 k = 0 #总计数

 while i < len(left) and j < len(right):
  if left[i] < right [j]:
  seq[k] = left[i]
  i +=1
  k +=1
  else:
  seq[k] = right[j]
  j +=1
  k +=1

 remain = left if i<j else right
 r = i if remain ==left else j

 while r<len(remain):
  seq[k] = remain[r]
  r +=1
  k +=1

 return seq

Method 2: In terms of taking values ​​in order, the list.pop() method is used, and the code is more compact and concise

#! /usr/bin/env python
#coding:utf-8


def merge_sort(lst): #此方法来自维基百科

 if len(lst) <= 1:
 return lst

 def merge(left, right):
 merged = []

 while left and right:
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))

 while left:
  merged.append(left.pop(0))

 while right:
  merged.append(right.pop(0))

 return merged

 middle = int(len(lst) / 2) 
 left = merge_sort(lst[:middle])
 right = merge_sort(lst[middle:])
 return merge(left, right)

Method 3: It turns out that the merge sort method is provided in the python module heapq. Just import the decomposed results into this method.

#! /usr/bin/env python
#coding:utf-8


from heapq import merge

def merge_sort(seq):
 if len(seq) <= 1:
 return m
 else:  
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])
 return list(merge(left, right))  #heapq.merge()

if __name__=="__main__":
 seq = [1,3,6,2,4]
 print merge_sort(seq)

For more detailed introduction to the implementation steps of the merge sort algorithm in Python programming, please pay attention to the PHP Chinese website!