Introduction to the method of merging sort using python programming

This article mainly introduces pythonProgramming to everyone in detail. The specific code to implement merge sorting has certain reference value. Interested friends can refer to it

Because of a question on leetcode last week (Median of Two Sorted Arrays), I wanted to take a closer look at the implementation of merge sort.

Let’s first explain the sorting idea:

First of all, merge sorting uses the dichotomy method. In the final analysis, the idea is to divide and conquer. Get a long array, divide it into the left and right parts continuously, and then divide it recursively. Then merge them into two ordered arrays. It may be difficult to understand in this way, so I will give you a picture I drew.

This shows the first step of merge sorting, recursively split the array according to middle, and finally divide it into the smallest details. It sorts two sorted arrays using the same method as sorting them.

Two sortedThe method of sorting arrays is very simple. Compare the first positions of the two arrays at the same time, put the smaller one into an empty array, and then put it The pointer of the position in the empty array is moved back by one, and then continues to be compared with the previous position of the other array, and so on. When the last array is popped off the stack first, all the elements in the other array will be appended to the new array.

Since the time complexity of recursive splitting is logN, however, the complexity of the method of sorting two ordered arrays is N. The time complexity of this algorithm is N*logN, so it is NlogN.

According to this wave of analysis, we can look at a behavior of the above picture.

When the leftmost one is divided into the smallest details, it can no longer be divided into the left and right parts and then starts to merge.

The first combination completes the merging of [4, 7]

The second combination completes the merging of [4, 7, 8]

The third combination completes[ The merging of 3, 5]

The fourth combination is completed The merging of [3, 5, 9]

The fifth combination is completed [3, 4, 5, 7, 8, 9] The merge ends sorting.

Put the python code below

def merge(a, b):
 c = []
 h = j = 0
 while j < len(a) and h < len(b):
  if a[j] < b[h]:
   c.append(a[j])
   j += 1
  else:
   c.append(b[h])
   h += 1

 if j == len(a):
  for i in b[h:]:
   c.append(i)
 else:
  for i in a[j:]:
   c.append(i)

 return c


def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 middle = len(lists)/2
 left = merge_sort(lists[:middle])
 right = merge_sort(lists[middle:])
 return merge(left, right)


if name == 'main':
 a = [4, 7, 8, 3, 5, 9]
 print merge_sort(a)

The above is the detailed content of Introduction to the method of merging sort using python programming. For more information, please follow other related articles on the PHP Chinese website!