Fastest Sort Algorithm

• Download source code - 20.8 KB
• Download Fastest_sort_algorithm - 10.2 KB

Introduction

This article is about In-place Merge Sort algorithm, fitted with parallel processing and providing with translation reduction between cache and main memory. I wrote the previous version at the time I confirmed the breakthrough idea's operation. It included many incomplete parts. I have considered all and it reaches almost consistent level. So I revise this edition.

I don't change my opinion "this is the fastest sort algorithm" at all. However, the present level is only a confirmation of the operation by C#. Program of C# never works fastest. However, I think this article content is useful to some readers annoyed by slow sort speed.

If I will explain in detail, this article will become as long as a book. So I apologize, this article is only summary level. I hope you to read the attached C# list and figure out the parts that have not been explained in this article. I intend to take care of easy expression of the program (though some rules are not common).

The Article Body

Competition of Sorting Time

The time that CPU executes sorting process is expressed by the below formula.

Sorting time = (1)The time of sort process itself + (2-1) One data comparison (evaluate) time * (2-2) comparison count + (3-1) One data move time * (3-2) move count

(1) can be ignored because of too small against others. (2-2)(3-2) are values showing sort algorithm speed. I measured representative sorting algorithm (Sortings.cs) counts actually.

I omit all algorithm explanation because it can easily be searched on the internet.

To make clear the fairness of count to all algorithm, data encapsulation prohibits each algorithm to operate data directly. (DataArray.cs)

I omit Radix sort because it is not valid to whole sort demand.

And I give up below commonly known hybrid algorithms measurement. The implant of count process for these original program is, I can't judge whether these implants are correct or not. Converting the process to this program shape for measurement is difficult and I can't judge conversion is OK or not.

These sortings are classifiable to below 2 tribes. I recognize each one is an improvement of these base and not too far from.

• <Quicks> GNU QuickSort, Pattern-defeating QuickSort (PdqSort), IntroSort
• <Merges> TimSort, QuadSort, GNU Stable Sort, Block Sort

The result table is below.

8/10/12 elements' values are all combination results. 100/512/1000 elements' values are the result of the same number sorting cycles.

This is my PC ability limit to end test within realistic time and to retain measurement data.

Each algorithms nature seems to be more clear than conventional landau symbol and sorting time test result.

QuickSort/HeapSort/Merge Sort Bottom up approaches have 2 types. One is original. The other is a faster version altering as small as possible the wasteful part.

QuickSort faster one is very ugly. GNU QuickSort waives before such and does Insertion sort at last. GNU QuickSort is right for practical use. My one is only an experimental try.

I choose my idea, as Merge Sort Bottom Up approach, fixing sort size to 2^N, by the reason of commonality to In-place Merge Sort of next chapter. This speed up version uses the way only possible in object-oriented language. QuadSort has done the same level move count decrement to any buffer copying. So QuadSort is better than this in Merge Sort using buffer.

In usual time measurement tests, one process time of both comparison and move is almost the same. By that, addition value of comparison count and move count in this table can be regarded time measurement test result. Seeing this table, QuickSort values are well-balanced both comparison and move. It agrees with the result QuickSort is fastest in time measurement test.

I warn you of one thing here. One move process time is almost the same both time measurement test and fact sort. One comparison process time of fact sort becomes larger than test. This is the main factor that sorting needs time. QuickSort comparison count is not smallest. Merge Sort is smaller.

I did a time measurement test of GNU QuickSort and In-place Merge Sort, that I explain later. GNU qsort is clearly faster in pure time test. But only adding 1usec wait to comparison process, In-place Merge Sort becomes faster. Merge Sort is better for heavy comparison process sorting. (I think it is common sort demand.)

If you see this table carefully, you may find an objection. In fact, the smallest comparison count sort is Binary Insertion Sort. Its move count is too large. So it never be the fastest in time measurement test. Array sorting is an unspoken agreement. Its move count in array sorting is O(N^2). But in linked list, its move count is O(N). Isn't data structure:"Linked list" and algorithm:"Binary Insertion Sort" combination fastest? For the confirmation of it, I attach linked list structure to array.(DataList.cs) Below table is its count measurement result.

I attach this linked list part into sort process. It is smallest count sort algorithm both comparison and move. "Binary Insertion using tiny Linked List sort", I named it BillSort for short. I did time measurement of it. Contrary to expectation, it is very slow speed endless sorting.

I pull out the slow point to below. It takes time more than 10 times of other total. If thinking only CPU process time, we never understand what wastes such a lot of time.

for (index k = half; k > 0; k--) {
    j = Next[j];
}

The endless reason is the transfer process time between cache and main memory of O(N^2). We can't hope fast speed to the algorithm using linked list.

It is sure that this CPU processing time is minimum in all sorting algorithm. If whole RAM of the computer works L1 cache speed, it will gain the fastest position. Such computer may come out in the future. So I place it in this article. But as a process in present PC, I throw away the possibility that Binary Insertion Sort becomes fastest.

We must be conscious of memory access of the process, not only CPU execution time.

In-place Merge Sort

I conclude in the previous chapter that Merge Sort is suitable for general sorting.

But there is one problem. Merge Sort is not In-place. Area O(N) except for sorted array is necessary. I think it is silly problem now from next things. Whole array data copy is not necessary. And present PC memory size have become sufficiently large from the time it was born and discussed.

But thinking cache, In-place Merge Sort is desirable and I have made the algorithm I show now. The base methods are Bottom Up approach and size limitation to 2^N.

Below three realizations are necessary for it. (InPlaceMerge.cs)

1. Exchange process of different size 2 areas that sit side by side.
2. Different size 2 areas merging. Fast process investigation.
3. In-place Merge Sort move count is O(NlogN^2). Not-In-place Merge Sort move count is O(NlogN). When array element amount is large, Not-In-place surely got ahead of In-place. So O(NlogN) method of In-place is necessary.

(1) Exchange process of different size 2 areas that sits side by side.

Shifting elements one by one. The method comes first of all. Knuth supposed the faster idea, but there is still no realized program. That's all I found in internet articles.

But already good way is used in GNU stable sort. Reverse each area independently. And reverse both connected area.

Before knowing it, I found out a different way.

• Shift smaller area to its integer multiple length. (This length must not exceed larger area length.)
• If (larger area)/(smaller area) = integer, this process finishes. Otherwise, do the same 1.process between shifted smaller area and surplus area of larger area.
• Repeat it until reaching.

It is just the same algorithm as greatest common divisor calculation. I name it GCD exchange.

Supposing each area size M, N. GNU always needs 2(M+N) move. GCD needs minimum (M+N) and it is convergent until 2(M+N). Measurement result is below table. And it can divide shifting size within cache size. I think GCD is superior to GNU in practical use. This program list seems a little complex. But supposing that it is realized on logic circuit, it is the same level of complexity as other ways.

(2) Speed investigation of different size two areas merging.

Generally Merge Sort means Top Down. Bottom Up is sometimes no regard.

We can see in the previous chapter table that Top Down Merge Sort is faster than Bottom Up in some points. Top Down always does the almost same size merge. Bottom Up must do largely different size merge in some case. We must consider this correspondence for speed up.

Below is the table of the case merging 1 ~ 8 elements into 8 elements. Combination of top element location of 1 ~ 8 elements in 8 elements area (9 location).

This is Σ formula calculation we learned in high school.

• More than half (4 ~ 8 elements): Merge from top as usual is no problem. (Preciously saying about 4~7 elements, next of top is its center location.)
• 1 element: Binary search and Insertion. Binary Search itself.
• 2 elements: Calculation of multiplication, and subtraction of decrement value. Serious calculation is not burden for CPU.
• Others : Calculation of N-power formula, and subtraction of (N-1)-power formula. When element amount is large, it exceeds negligible time and complexity. It is not result but initial value of searching. So I decided start value around. When element amount exceeds 2, calculate 2 elements value and multiply 1/2^(N-2). It is this time approximation.

This alteration is already done to the above result table. So the counts are improved from the previous article.

(3) Making In-place Merge Sort exchange count to O(NlogN)

I said in the previous article, when data amount is large, switching to Not-In-place Merge Sort was necessary.

O(NlogN^2) is absolutely decition thing as long as merge starts from top. But I have found an idea to decrease move count of In-place merge.

Merge from the center, and do area division, like Quick sort. At first, get one center element from large area. Search its insert location in small area. The probability density would be mountain shape that center is highest. So search from center, by 1 step, in small area. One merge is divided into 2 small merges. Massive area moves at once and sum of move count decreases straight away. I name it center-to-center merge.

Its Landau symbol N degree clearly goes down. But I can't fix that it is truly O(NlogN), because I am not mathematical theory expert.

Comparison count increases. It has sub effect.

But it has clear merit.

• Compared to original merge, the transfer interval between cache and main memory is reduced.
• Plural merges can be processed in parallel processing.

Not-In-place merge using buffer can't realize this. The algorithm becomes pure In-place Merge Sort process, leaving from the spell.

Switching 2 In-place merge methods seem good. Within the cacheable size, merge using "from top" methods and make sorted blocks. When the size exceeds cacheable, merge using center-to-center merge method.

I think it comes almost terminus of In-place Merge Sort on single core. Though some adjustment may be necessary, necessary technology should have already come out. "Merge, In-place, Cache adaptable, Exponent of 2 (2^N)", I name it MiceSort for short.

In measurement result, comparison count is almost the same as the original and move count decreases. I have converted it to C-language and done time competition with GNU qsort. It is slower than qsort when comparison process is pure comparison only. But it becomes faster when comparison process includes 1 usec wait.

Parallel Sorting

In-place merge process can be transformed to Parallel processing.(Parallel.cs) I intend to make documentation about this process as well as possible.

1. Run sort robots as same amount as CPU multi-core. These robots do the same operation. Each robot cleans up the sort process independently. When all sort process is tidied up, the sort is ending.
   
   If same cleaning robots all you have run at the same time, spacious room cleaning time is shortened to 1/(robot amount). That is this process image.
   
   We have been experiencing break down of "Unhandled exception" or deadlock, when we run tasks one after another asynchronously at any parallelizable points. Even if we intend to limit task to core amount, we will encounter exception of unsure reason by silly modification.
   
   One radical settlement is to stop parallel processing. Another is the method shown here. The same amount of tasks as core keep on running. Otherwise, no one can predict the parallel process works safely on any circumstances.
2. Divide sort data into cacheable size blocks. One process changes these blocks into sorted blocks. Other process merges these blocks into merged blocks and merge to higher level. These 2 states are necessary.
   
   Prepare a array showing each block situation, not-sorted or under sorting or sorted, and block size. Each sort robot refers this array and knows unprocessed things and cleans up what it must do.
   
   At the time top level merge finished, the sort is completed.
   
   Sort data are nonuniformity, mix of almost sorted place and random place. Cache size block have effect to smooth workload of each core, too.
   
   Previous article ended here. While climax large merging, operating cores faded away one after another. Top level whole array size merge was done by one core totally. It is very wasteful for CPU including many cores. I add next process.
3. In merge process of sorted blocks, use center-to-center merge method. By that, the merge process is divided into many merges. Push these merges to stack. When all merges in stack is cleared off, the merge finishes.
4. Make management center that all stacks of each core are got together. This center can be referred from every core. When all job it must do is end, the core gets a merge from this center, largest merge of stack bottom.

By that, each core works parallelly until the very end.

I name it "Both sides now sort". From song "Both sides now" lyrics.

Though present situation is not cheerful, I believe this is the fastest sort algorithm, and it almost reaches near to possible limit of sorting on multi-core CPU, and it is basement of future parallel sorting.

I use goto sentence in this program list. In fact, I made goto-less structured program, but I threw away it because it is difficult to guess the process purpose. To keep process order from top to bottom is impossible now, by the obstruction of parallel, asynchronous, callback, etc.. For the readable description, using goto sentence efficiently is necessary now. It is my opinion.

Notes of Attached Program

One is that it sometimes judges sorting is not good.

If you encounter the problem in the execution of attached list, you must increase number of Sleep(1) in the program to OK value. 1usec is number for small data element.

I know lock is necessary to this settlement. But lock makes slow the sorting. I judged wait time after sorting is better.

Another is present program doesn't work fastest. It is slower than single core Mice Sort. Though the reason may be I test it on i5 note(2 core).

But I think alteration point still remains. I have used lock sentence everywhere conflict can occur for safety. I already know some lock can be vanished. Reconsideration around lock is necessary.

Speed check on Windows C# may be meaningless. The process time varies largely by conditions, only moving process location, and Visual Studio runs or not. I can't stop background task of Windows.

Left Things

The attached program includes constant like cache size. The value in it is empirically fast value on note i5. It is not adapted to theoretically fastest value. It should differ by CPU and it should differ on your PC. In fact sorting, if comparison process of the sort uses many work areas or table, this value should differ. On little core CPU like the one I use now, OS task should occupy some cache of sorting core. Still, I have seen the speed difference with the change of these constant in this experiment. Because CPU has plural level caches, the consciousness to cache in the program affect to speed.

Fix of the value is impossible for me. The person who can do it is a CPU maker engineer knowing cache control logic.

Or only user programmer can define the efficient value to his purpose.

I attempted to convert "Both sides now sort" to C-language for the competition with qsort. But C-language parallel process is environment‐dependence. C# shape is easy and convenient for me even if it is slow. Even if converting program working on Linux, it is meaningless for me. I don't have expensive many-core PC. Until no environment‐dependence parallel sentence of C-language comes, I postpone it.

I intend to alter around lock before that.

Though I feel this may be the last one, I write about this theme.

History

• 19^th August, 2020: Initial version
• 27^th January, 2020: Updated article and source code