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

Python in how to achieve merger sorting, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Merge and sort

Merge sorting is the application of divide-and-conquer strategy in sorting.

Merge sorting is essentially a recursive algorithm, the idea is to continuously split the data table into two halves, and merge and sort the two halves respectively.

The basic end condition of recursion: there is only one data item left in the data table (at this time the whole data table has been sorted)

Downsize: split the data table into equal halves so that the size is halved and moving towards the basic end condition

Call yourself: call the two halves separately to merge and sort, and then merge the two halves of the sorted parts to get the sorted data table.

Specific steps for merging and sorting (two parts):

First, divide the data table into two points all the time, and in the end, there is only one data item, so you can't divide it any more.

Start merging and sort when merging

Code thinking

Using recursive calls to split the data table

After the recursion is over, the left and right parts of the data have been sorted.

Compare the left and right parts one by one, extract the small ones and put them in the list of results.

Zipper interlacing merges the left and right parts into the result list from an early age

Finally, if one party is emptied, the rest are big data items and orderly. Directly behind the result list.

Split method: array slicing

The method of merging: compare the left and right parts of the array element by element (loop condition, there are elements in both parts)

Algorithm analysis

There are two main processes in merger sorting: splitting and merging.

Split: O (logn) reference binary search

Merge: O (n) all elements are compared once

Time complexity of merge sorting: O (nlogn)

In terms of time complexity, the efficiency of merge sorting is very good. However, it should be noted that in terms of space performance, merge sorting requires twice as much storage space for the merge process, which is a disadvantage of big data.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.