How to realize merge sorting in Python

This article shows you how to implement merge sorting in Python, concise and easy to understand, absolutely can make your eyes shine, through the detailed introduction of this article I hope you can gain something.

1, merge sorting principle

Merge sort uses the divide-and-conquer principle:

1. Divide a sequence into two sequences from the middle position;

2, dividing the two sub-sequences into two according to the first step;

3. Until all sub-sequences have a length of 1, that is, no further binary cutoff can be made. At this time, two more can be combined into an ordered sequence.

2. A picture to show it

3. Python code

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)