Hello, Data Structure and Algorithm,. This lesson, let’s continue the study of chapter 8, internal sort. Today, we study merge sort.
The concept of merge sort is a classic idea of divide and conquer.
We divide the sequence waiting for sort into 2 subsequences.
Then,divide each subsequence according to idea of merger.
After we get tow ordered subsequences, we merge them.
For such a sequence waiting for sorting,we continue division until each subsequence is ordered.
Actually, sequences contains one element is already ordered.
Next,we merge the every tow neighbor subsequences into a single bigger subsequence.
And do the same layer by layer.
Finally, we get a result of sort.
Let’s look at the frame of merge sort.
For such an array waiting for sort.We need to open up a temporary array as big as it to store the temporary data during the process.
We give the left subscript and right subscript of the array.
Then we divide it equally.
After that, we handle this two parts recursively in the same way.
The left and right subsequences we get are already ordered.
Next,we merge this ordered subsequences.
Let’s look this merger operation. These two subsequences are both scanned from left to right, and then merged into a new array.
At beginning, we store all the elements waiting for sort into a temporary array.
Then, we set tow subscripts, the subscripts are left-most of left array and right-most of right array respectively.
Next, our resulting array starts from the subscript left.
These two ordered array are bounded by these two subscript. And these two subscripts can’t cross the border.
Which means the left subscript can’t cross the subscript middle.
and the right one can’t cross the subscript right.
In the bound, we compare the first element of these two subsequences. And find which one is smaller.
The smaller one will be put on the position i of the resulting array.
And this subscript changes too.
The subscript of the sequence contains the smaller elements changes as well.
Here, we should especially notice that we prefer the left element when we compare the header element of two subsequences.
Which means we choose left one when the two elements are equal.
In this way, we can guarantee the stability of the sort.
after being out of the loop
there may be only left sequences left. And the right one is handled completely. Which means the bound is unsatisfied.
Or on the contrary. but these two situation can’t occur concurrently.
In the other words, there will only left sequence or right sequence left. We just need to copy the elements of left sequence to the resulting array one by one.
Then the process of merger is finished.
Just like quick sort, we need to optimize the merge sort.
Especially for some small sequence, it’s unnecessary for us to handle it recursively because of the expensive cost of recursion.
For example,we need to prepare the stack space for recursion,and function call also spend some time.
For the mostly ordered small sequence,we use a simple sort algorithm.
There is another optimization presented by Sedgewick.
Let’s recall the previous algorithm, we need to consider whether the subscripts of subsequences are in the bound.
Which means index1 can’t cross the value of middle,
and subscript index2 should be smaller then or equal to right.
The check is implemented by using if judgement. But the cost of if judgement if is large.
Our optimization works from both ends of array to middle.
Of course, the right subsequence is reversed.
Which makes the last element of our left and right sequences are neighbor. They are back to back and monitor each other.
In this way, we can simplify the check of bound and speed up our algorithm
Let’s look the concept of Sedgewick optimization.
It is same in the partition. In the merger, we reverse the right subsequence.
So, the biggest element of these two subsequences are neighbor and play the role of monitor.
When we merge these elements, our subscript can move from both ends to the middle.
So there is no need to consider whether they are in the bound.
Because once it cross the bound, for instance,this 45 of left sequence is handled now, then the subscript will changes to position of 78.
in this way, it is obvious that the residual element 64 is definitely smaller then 78.
So it wouldn’t cross the bound.
Let’s look a demonstration of it.
At first, these two elements are convenient during the process of merger.
For the array which length is 2, you can see that we reverse it here.
Then, you can see these two subscripts, if one is already handled, it will overlap with the left bigger subsequence and become a monitor.
Let’s look a bigger example. After reversion, we work one by one.
After the sequence contains 45 is already handled,it’s subscript li will move to this position, and block the element of i2’s array naturally.
Let’s look the frame of this algorithm.
At the optimization, we firstly eliminate the recursion for small subsequences.It’s is implemented by this sentence.
which means if length of sequence is smaller than the threshold value, we directly using insert sort.
In the different operation system, the threshold value we get from test is different. You should test according to your application environment.
Not all the threshold value are equal to 28,Just in our example, in is 28.
Let’s look the rest of code.The partition is same.
Then these two recursion, look like same.The mainly difference is in the merger of neighbor ordered sequences. let’s look how does it work.
During the process of merger, we know we need a temporary array.
The left subsequence is just as same as original. And for the right subsequence we store it in the temporary array, and then be reversed
In this way, we reach the goal that these two index play the role of monitor for each other.
In this way, we just need to scan it
and we can guarantee the whole subsequence is moved to targeted array.
In the process of compare, we can only compare the value of element of index1 and index2.
Then the smaller one will directly move to resulting array.
In addition, it’s index field should be add by 1.
In this way, we greatly simplify the process of merger.
Especially for judgement of bound and work at the end which means we need to copy the another sequence after some subsequence is handled completely to the resulting array.
But in this algorithm, once one of subsequences is handled completely, the index of it just cross to last position of the another array wherever you come from.
So it can play the role of monitor, and we can work uniformly and length of code is shorter.
Ok, let’s look other things. Cost of time and memory.
At first, the cost of memory is expensive.It need to use an array as big as the array waiting for sort, so it is Θ(n)
As for time, we look it according to division, conquest, merger these several parts.
For division, it’s simple, divide by 2 then you find the division point.
Then for sort, actually it is a process of recursion.
If we assume the time of such a merge sort as T(n).Then it is divided into two sequences which size is n/2.
So the cost is 2 times T(n/2)
As for time of merger, a sequence whose length is n is generated by merging two subsequences whose length is a second of n;
We have to scan these two subsequences. So we add cn which c is a constant。
For situation which scale is small, we can define it as a constant
Like previous quick sort, in the best case,for such a recursive expression, we can calculate the total cost of time of merge sort is Θ times log n
It totally doesn’t relay on the original input array.
In the best or worst or average case, the costs are all Θ(n) times logn.
Finally, I left you some question.
First one is this, is normal merge sort or Sedgewick merge sort stable?
It need some consideration, one of them are unstable.
In addition, which one of these two algorithms is better on the cost of time.
We can consider it according to the number of compare, number of assignment, etc.
You should especially notice if we need to check whether the subscript of the subsequence is in the bound
We know that there is no need in Sedgewick algorithm, and what benefit would it produce? You should consider it carefully.
Thank you.