


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!

This tutorial demonstrates how to use Python to process the statistical concept of Zipf's law and demonstrates the efficiency of Python's reading and sorting large text files when processing the law. You may be wondering what the term Zipf distribution means. To understand this term, we first need to define Zipf's law. Don't worry, I'll try to simplify the instructions. Zipf's Law Zipf's law simply means: in a large natural language corpus, the most frequently occurring words appear about twice as frequently as the second frequent words, three times as the third frequent words, four times as the fourth frequent words, and so on. Let's look at an example. If you look at the Brown corpus in American English, you will notice that the most frequent word is "th

Python provides a variety of ways to download files from the Internet, which can be downloaded over HTTP using the urllib package or the requests library. This tutorial will explain how to use these libraries to download files from URLs from Python. requests library requests is one of the most popular libraries in Python. It allows sending HTTP/1.1 requests without manually adding query strings to URLs or form encoding of POST data. The requests library can perform many functions, including: Add form data Add multi-part file Access Python response data Make a request head

Dealing with noisy images is a common problem, especially with mobile phone or low-resolution camera photos. This tutorial explores image filtering techniques in Python using OpenCV to tackle this issue. Image Filtering: A Powerful Tool Image filter

This article explains how to use Beautiful Soup, a Python library, to parse HTML. It details common methods like find(), find_all(), select(), and get_text() for data extraction, handling of diverse HTML structures and errors, and alternatives (Sel

PDF files are popular for their cross-platform compatibility, with content and layout consistent across operating systems, reading devices and software. However, unlike Python processing plain text files, PDF files are binary files with more complex structures and contain elements such as fonts, colors, and images. Fortunately, it is not difficult to process PDF files with Python's external modules. This article will use the PyPDF2 module to demonstrate how to open a PDF file, print a page, and extract text. For the creation and editing of PDF files, please refer to another tutorial from me. Preparation The core lies in using external module PyPDF2. First, install it using pip: pip is P

This tutorial demonstrates how to leverage Redis caching to boost the performance of Python applications, specifically within a Django framework. We'll cover Redis installation, Django configuration, and performance comparisons to highlight the bene

Natural language processing (NLP) is the automatic or semi-automatic processing of human language. NLP is closely related to linguistics and has links to research in cognitive science, psychology, physiology, and mathematics. In the computer science

This article compares TensorFlow and PyTorch for deep learning. It details the steps involved: data preparation, model building, training, evaluation, and deployment. Key differences between the frameworks, particularly regarding computational grap


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

WebStorm Mac version
Useful JavaScript development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

SublimeText3 Chinese version
Chinese version, very easy to use

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Dreamweaver Mac version
Visual web development tools
