Quick sort (non recursive) and merge sort

We know , When there are more recursive levels of quick sort , Then the stack may overflow . So we need to write a non recursive .

1. Quick sort ( Non recursive )

So how do we change recursion to non recursion ？
We need to take advantage of the stack data structure .
Let's look at the following set of data ：

First , We put the subscript of the first element and the subscript of the last element on the stack ：

then , We will 9 Take it out and put it in right, take 0 Take it out and put it in left in , Then do a single sequence .
This is how the order is arranged ：

then , We are going to 6 What should I do if the left and right intervals of are ordered ？ We will 0 and key-1 Push , And then key+1 and n-1 Push .

We will 9 Put it in right, take 6 Put out of stack left, Then do a single sequence .
That is to say 6 Do single pass sorting in the right section of ：

then , We will again 9 Stack the left section of ,9 Stack the right section of .
because ,9 There is only one number in the right section of a, which does not need to be put on the stack , Only enter the left section .

then , We will 7 Put out of stack right in , take 6 Put out of stack left in . Then do a single sequence ：

here , We will 8 Stack the left and right intervals of ,8 There is only one left section of that does not stack ,8 The right section of does not have or is not stacked . here , There are still... In the stack 0 and 4, That is to say 6 Left interval of , The idea is the same .
Complete code ：

In the same way , We can also use queues to implement .

2. Merge sort

2.1 The basic idea

Merge sorting is an effective sorting algorithm based on merge operation , This algorithm is a very typical application of divide and conquer method . Merges ordered subsequences , You get a perfectly ordered sequence ; So let's make each subsequence in order , Then make the subsequence segments in order . If two ordered tables are merged into one ordered table , It's called a two-way merge . The core steps of merging and sorting ：

Dynamic diagram demonstration ：

2.2 Implementation of recursive version

In fact, we just decompose the sequence into subproblems that cannot be decomposed . It's just 1 Sometimes or not , We can start merging .
When merging, we need to create an additional array , Because if you merge in the original array , Will overwrite the value .
First , Let's look at the decomposed code ：

When begin and end All for 0 when , Just go back to , Then recursive right interval ,begin and end All for 1 when , return . here , We can merge [0,0] and [1,1] The value of two intervals . Other principles are similar .

that , Talking about how to merge ：

Let's take this set of sequences as an example ：
First , We need to [0,0] and [1,1] Merge , It's about comparing the size , Put the small ones first tmp In the array , Then continue to compare . When the merge is complete , We will tmp Copy the data in to the original array .

such [0,1] The intervals are ordered , We started merging [0,1] and [2,2]

such [0,2] It's in order , We need to merge [3,3] and [4,4]

such [0,2] and [3,4] It's all in order , We need to merge [0,2] and [3,4]

So the left section is in order , The same is true for the right range .
The complete code is as follows ：

2.3 The non recursive version is specifically implemented

First , Let's look at this set of data ：

If we go back , You need to go back one by one ,10 and 6 return ,7 and 1 return ,3 and 9 return ,4 and 2 return .
So we can define a gap Represents the number to merge .
When gap by 1 when , That is, merge one by one .

then , We will gap by 2, This is the merger of two .
That is to say [0,1] and [2,3] Merge ,[4,5] and [6,7] Merge .

Then there is the four four four merger ,[0,3] and [4,7] Merge .

From here , We can see that gap from 1 become 2 And then it becomes 4 yes 2 Times the growth .
Then we can control gap 了 ：

then , We need to control the array subscript , We can define one i To control , The first step is the subscript 0 And subscripts 1 Merge , The second step is the subscript 2 And subscripts 3 Merge … That is to say i=0,i=2,i=4…
When two are merged ,[0,1] and [2,3],[4,5] and [6,7], That is to say i=0,i=4,i=8…
Then we can control the subscript ：

Is there any problem with this writing ？ Let's look at the following data ：

If gap by 2 when , That is, two by two .[0,1] and [2,3] Merge ,[4,5] and [6,7] Merge ,[8,9] and [10,11] Merge , however [10,11]begin2 and end2 It's crossed the border .

When gap by 4 when , Namely [0,3] and [4,7] Merge , then [8,11] and [12,15] Merge . At this time end1,begin,end2 It's all out of bounds .

So we have to think about how to solve this cross-border problem .
From the above analysis, we can conclude that ,end1,begin2,end2 May cross the border . So we need to control the three cross-border .
There are three cases here ：
Case one ：end1 Not across the border ,begin2 Not across the border ,end2 Transboundary . So if end2>=n when , We will end2 Assigned as n-1

The second case ：end1 Not across the border ,begin2 Transboundary ,end2 Transboundary . Then the second interval does not exist , We will make the second interval into a nonexistent interval

The third case ：end1 Transboundary , that begin2,end2 It must have crossed the line . So we need to end1 Assigned as n-1,begin2 and end2 Modify according to the above .

In this way, the non recursive boundary problem can be controlled . The complete code is as follows ：

2.4 Complexity analysis

2.4.1 Time complexity

Let's talk about time complexity first .

Merge sort is divided into decomposition and merging . First of all, we can see that it is a quadratic bisection every time . altogether n Number , Every time it's two points , That is to say 2^x=n,x=logn. therefore , Decomposed into logn layer .

Merging is much like decomposing , But merging requires sorting , That is to say, every time you merge, you have to go through it n, Then there is logn layer , That is to say n*logn.

So the time complexity is logn+nlogn, At large O The asymptotic representation of is O(nlogn).

2.4.2 Spatial complexity

The spatial complexity is very simple , We can see that it needs additional development n A data space . Then we'll look at its recursion depth , We can see that it recursively has logn layer , The space in each recursion is a constant number , That is to say O(1), therefore , The spatial complexity is n+logn, Again because n Far greater than logn, So the space complexity is zero O(N).

2.5 The outer sort of merge sort

In these common algorithms we are talking about , Can achieve internal sorting . What is inner sorting ？
Internal order ： Data is stored in memory . Subscript random access , Fast .
however , Only merge sort can do outer sort .
So what is outer sorting ？
External sorting ： Too many data elements to be in memory at the same time , And put it on disk , Serial access , Slow speed .

Now there's a question ：
10 Billion integer files , Only to 1G Running memory , Please check the... In the file 10 Hundreds of millions of them .
How can we solve this problem ？
First , We need to know 10 How much memory do we need for 100 million integers ？
1G=1024MB,1024MB=10241024KB,1024KB=10241024*1024byte
therefore 1G Approximately equal to 10 Gigabytes . that 10 A hundred million integers is 40 Gigabytes , Is almost 4G.
resolvent ： Divide the file into 4 Equal division , Each for 1G, Read and sort in memory respectively , Ordering , Then write back the small file on the disk . Then merge in the disk .