Artificial QuickSort
Updated: 10.04.2007 19:00 CET

Here we are. A new sorting algorithm has been invented, using the Critticall programming tool. It's worth to mention, since it's faster then QuickSort. In fact it degenerates to some kind of (fast!) QuickSort, when purely random arrays are to be sorted. For more frequent everyday arrays with some equal elements, it's significantly faster than the old champion.

You are free to test it and use it every way you wish, the code is bellow the gif algorithm demonstration.

Artificial QuickSort                            QuickSort
with InsertionSort                        with InsertionSort

Show ORTO Artificial QuickSort source C++ code
ORTO means strictly comparison version of the Artificial sort. A little slower but still faster than Quick sort

Use this algorithm every way you want. Especially for large arrays the difference may be substantial. Everything comes down to the fact, that the information that something is already sorted is used on one hand, and that the middle point between two unsorted elements is generally a good pivot - on the other.

As this algorithm somehow managed to escaped every human to spot it for the past forty years, it's quite conceivable, it's not the end of the story, yet. Stay tuned for further advances or try it for yourself, using Critticall.
The main innovation compared to the QuickSort is: Don't sort an already sorted segment!. A lot of repeating partitioning can be avoided, if the already ordered segments are just tested once and left alone - no additional tests, let alone additional partitioning. For the QuickSort, a sorted segment is a subject of maybe a lot of the repetitive comparing, partitioning and stacking. Artificial QuickSort can harness the order it encounters. What often gives it a considerable edge.

Comparison table:

AS - Artificial QuickSort with InsertionSort
QS - QuickSort with InsertionSort

 NumberOfRec = 30.000.000 NumberOfRec = 10.000.000 NumberOfRec = 1.000.000 Data = Rnd(-10000000, 10000000) AS = 12437 ms QS = 12781 ms AS = 3968 ms QS = 4046 ms AS = 343 ms QS = 359 ms Data = Rnd(-1000000, 1000000) AS = 10500 ms QS = 11828 ms AS = 3563 ms QS = 3891 ms AS = 344 ms QS = 360 ms Data = Rnd(-100000, 100000) AS =  8562 ms QS = 10812 ms AS = 2859 ms QS = 3484 ms AS = 313 ms QS = 343 ms Data = Rnd(-10000, 10000) AS =  6875 ms QS = 10078 ms AS = 2313 ms QS = 3188 ms AS = 219 ms QS = 282 ms Data = Rnd(-100, 100) AS =  3703 ms QS =  8407 ms AS = 1234 ms QS = 2656 ms AS = 125 ms QS = 234 ms Data = Rnd(-10, 10) AS =  2094 ms QS =  7640 ms AS =  703 ms QS = 2453 ms AS =  78 ms QS = 203 ms

Demonstration:

Every vertical line represents the array and every pixel is an element. Bigger (brighter) and smaller (darker) are randomly mixed on the left side and sorted on the right. The transition during the program's execution is clearly visible.

What has really happened that day, back in 2007, when the ArtificialQuickSort was born? We have just realized then, that the Several Unique Sort, which has evolved further to the Two Unique in the environment of exactly two different keys to sort, has a potential to partition a file into two parts. Those greater than the pivot and those not greater than the pivot. Whatever the pivot may be. So, we wrote the code. After some additional cooking inside Critticall, we basically got what is now the Artificial QuickSort.

One may ask, what is the difference between Quick and Artificial? The answer is - in the partitioning! Artificial partitions differently or not at all, unless it's absolutely necessary.