Merge sort

Merge sort is a very typical application of divide and conquer method . The idea of merging and sorting is to recursively decompose arrays first , Recombine arrays .

After decomposing the array to the minimum , Then merge two ordered arrays , The basic idea is to compare the first two arrays , Take the first one who is small , After taking the corresponding pointer, move it back one bit . Then compare , Until an array is empty , Finally, copy the rest of another array .

Analysis of merge sort

def merge_sort(alist):
if len(alist) <= 1:
return alist
# Dichotomy
num = len(alist)/2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# Merge
return merge(left,right) def merge(left, right):
''' Merge operation , Put two ordered arrays left[] and right[] Merge into a large ordered array '''
#left And right The subscript pointer to
l, r = 0, 0
result = []
while l<len(left) and r<len(right):
if left[l] < right[r]:
l += 1
r += 1
result += left[l:]
result += right[r:]
return result alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = mergeSort(alist)

Time complexity

  • Optimal time complexity :O(nlogn)
  • Worst time complexity :O(nlogn)
  • stability : Stable

python Algorithm merge sort more related articles

  1. Python Sorting search basic algorithm merge sorting example analysis

    Python Sorting search basic algorithm merge sorting example analysis This article gives an example of Python Sort search basic algorithm merge sort . Share with you for your reference , As follows : The most exciting feature of merge sequencing is : Whatever the input is , It's right N The order of two elements ...

  2. install Python Algorithm library

    install Python Algorithm library It mainly includes the use of NumPy and SciPy To process data , use Matplotlib To realize data visualization . In order to meet the needs of processing large-scale data ,python On this basis, we developed Scikit-Learn Machine learning is ...

  3. Java Merge sort is a common sort algorithm

    In the process of learning algorithms , We will inevitably come into contact with a lot of sorting related algorithms . To make a long story short , For any programmer , The basic sorting algorithm must be mastered . Starting today , We are going to explain the basic sorting algorithm .Are you ready?Let ...

  4. python Algorithm ( One )

    python Algorithm ( One ) One . Counting x Factor of x=100 divisors=()# Initialize empty tuples for i in range(1,x): if x%i==0: divisors=divisors+(i, ...

  5. Python Algorithm and data structure -- Find the maximum sum of all subarrays

    Python Algorithm and data structure -- Find the maximum sum of all subarrays Xuanhun studio - Mysterious soul Secretary of xuanhun studio Xuanhun studio   yesterday subject : Enter an array of integers , There are positive and negative numbers in the array . One or more consecutive integers in an array form a subarray , Every ...

  6. Python Algorithm : deduction 、 Recursion and Convention

    Python Algorithm : deduction . Recursion and Convention notes : In this section, I give the Chinese translation of the following three important words :Induction( deduction ).Recursion( recursive ) and Reduction( Statute ) This section mainly introduces the three cores of algorithm design ...

  7. 【DS】 Merge sort of sorting algorithm (Merge Sort)

    One . Algorithmic thought Merge sorting is an effective sorting algorithm based on merge operation . This algorithm is a very typical application of divide and conquer method , It refers to the operation of merging two sorted sequences into one sequence . The idea of merging is as follows : 1) To apply for space , Make it the size of two already ...

  8. Merge sort of sorting algorithm (Mergesort) analysis

    from :   One . The advantages and disadvantages of merge sort (pros and cons) Take the trouble to understand it , There must be a reason : The efficiency of merge sort is up to ...

  9. python Merge sort in

    I saw it on my blog python Write merge sort program , Then I followed him to write , It turns out to be wrong , I have to do it myself . And I'm right python I don't know very well, so I changed to Baidu while writing , In the end, it took half an hour to write . def m ...

Random recommendation

  1. SpringMvc Custom interceptors

    SpringMvc You can also use interceptors to intercept requests , Users can customize interceptors to achieve specific functions , Custom interceptors must implement HandlerInterceptor Interface -preHandle(): This method is implemented in the business processor ...

  2. DFS/BFS Codeforces Round #301 (Div. 2) C. Ice Cave

    Subject portal /* The question : Tell the beginning and the end , Step on it once , '.' become 'X', Step on it again , The ice is broken , Ask if you can break the terminal ice DFS: As the answer says , There are three situations :1. If two points coincide , Just go out and come back :2. If two ...

  3. linux The file properties of 、 Directory and path representation

    One . know linux file know linux You need to learn the command first :ls. This command is used to display the contents of the specified directory , The most commonly used parameters are : -l Display the complete property information of directory and file -a Show all files and directories , Contains hidden files and directories ...

  4. Use the Heyuan model to solve DOM Too many elements lead to slow page parsing 、 Stuck problem

    I also don't know what kind of appropriate title should be chosen for this article , But I feel that it is in line with the idea of Xiangyuan mode . In some web applications , Sometimes you come across a huge list , Thousands of lines , At this time, most browsers are very painful to parse ( It's possible to get stuck ). ...

  5. NSDictionary summary -iOS

    summary : The dictionary is divided into NSDictionary( immutable , Can only query ) and NSMutableDictionary( variable . Can add, delete, and check ) Two kinds of , The form is key-value,key It can't be repeated ,value Can be repeated 1. Initialization word ...

  6. js,jq Get element location attribute and compatibility writing

    The height of the web page being rolled up / Width document.documentElement.scrolltop // firefox and Other browsers document.body.scrolltop   //ie, Google browser and no ...

  7. [ turn ]What is a WebRTC Gateway anyway? (Lorenzo Miniero)

    [ turn ]What is a WebRTC Gateway anyway? (Lorenzo Miniero) As I mentio ...

  8. Kubernetes Common architectures in production environments

    Kubernetes Common architectures in production environments First , Let's sort out Kubernetes Production structure , It's designed for most environments . As shown in the figure below In this schema , We can divide it into four layers , as follows : Client layer : namely Kuber ...

  9. Why Random Initialization in Neural Network?

  10. centos7.2 Lower installation Mysql note

    centos7.2 Lower installation Mysql note install MySQL Apply to CentOS 7.0 Or later : yum install mariadb mariadb-server Apply to CentOS 6.8 ...