Shulou(Shulou.com)06/01 Report--

This article is about how to use the merge sorting algorithm implemented by Python. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Introduction

Merge sorting (English: Merge sort) is an effective sorting algorithm created on the merge operation, the efficiency is. It was first proposed by John von Neumann in 1945. This algorithm is a very typical application of divide-and-conquer (Divide and Conquer), and each layer of divide-and-conquer recursion can be carried out at the same time.

Divide and conquer:

Segmentation: recursively divides the current sequence into two halves. Merge: merge (merge) the subsequences obtained in the previous step while maintaining the order of the elements. Graphic algorithm

After reading the above definition, if you feel a little confused, that's right, this article is for you. We introduce the flow of the algorithm in detail through pictures and text. The core of the algorithm is only four words segmentation and merging.

Suppose we sort the following sequence from small to large.

94, 45, 82, 33, 25, 59, 94, 65, 23

Of course you can sort the task manually quickly, but with 300000 numbers, you may be devastated. Let's take a look at this example and divide the sequence evenly. There are a total of 9 numbers. The middle position is 4.5 and the rounded result is 4. It is divided into two subsequences, the first four elements and the last five elements, and then recursively operate on the two subsequences until there is only one element in the subsequence.

Merge sort-split

The above steps complete the split, and then start merging. The smallest two subsequences are 94 and 45, so the two subsequences are merged to get the sequence [45,94], and the other subsequences are [33,82]. Then combining the two subsequences to get the left half [33,45,82,94].

Merge sort-merge

There are fewer elements here, and you may not see it clearly, so you get the left half of the ordered subsequence (the first four elements). In the same operation, we get the ordered subsequences of the next five elements, and finally merge the two subsequences. It will be explained in more detail below.

[33, 45, 82, 94]

[23, 25, 59, 65, 94]

The process of merging is the same, and the following gif dynamic diagram clearly demonstrates the merging process of two subsequences. Due to the limitation of the official account, the completed demonstration cannot be given. The full demo can be seen in the video below.

Reference code

The following is the code for the merge sorting algorithm implemented in Python, for reference only:

Import typing as t

Def sort (data: t.List [int]):

"

Sort data

"

If len (data)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.