Algorithms Discussion Boards

I've created a new sorting algorithm which allows O(1) sorting of ordered data, O(log (root n)) sorting of partially sorted data, and O(log n) sorting of random data.

The underlying mechanism is well suited for a general purpose data structure, which I'm calling a binary search cube, and has notable advantages over binary trees. The data structure is cube-shaped rather than tree-shaped.

I've described the data structure and sorting algorithm on the following webpage:

https://sites.google.com/site/binarysearchcube/

The site also includes three programs written in C, one of them implementing cubesort using a 4 dimensional search cube, and an implementation of a 3 and 4 dimensional binary search cube.

Haven't been able to properly benchmark the software against other sorting algorithms and data structures, but the memory overhead is significantly less.

Hoping for some interesting feedback.

Hi Mr. Hoven,
looks nice feels exciting, surely the showdowns are gonna be must-see.

My suggestion is to make a simple console tool to ease the benchmarking, I will be the first to run some superheavy English phraselists/wordlists (up to 400,000,000 lines) on my laptop T7500.

One very useful filedataset is to sort Knight-Tours (64x2=128 bytes long lines), because you can generate even billions of them in reasonable time, my package (that do that) can be downloaded freely at: www.sanmayce.com/Downloads/Sandokan_r3_vs_Windows-sort.zip[^]

My old console sorter Sandokan outperformed (only for internal sorting) the built-in Windows 7 64bit sort.com:

E:\Sandokan_r3-+++\Sandokan_r3_vs_Windows-sort>GENERATE_3million_Knight-Tours_and_SORT_them.bat

Microsoft Windows [Version 6.1.7601]
Generating 3,000,000 Knight-Tours and dumping them into file 390,000,000 bytes ...

E:\Sandokan_r3-+++\Sandokan_r3_vs_Windows-sort>Knight-tour_r8dump_Microsoft_V16_32bit_Ox.exe a8 3000000  1>KT3million.txt
Sorting these 3,000,000 Knight-Tours ...

E:\Sandokan_r3-+++\Sandokan_r3_vs_Windows-sort>"Sandokan_QuickSortExternal_4+GB_32bit_Microsoft.exe" KT3million.txt /fast /descend 768
Sandokan_QuickSortExternal_4+GB r.3, written by Kaze, using Bill Durango's Quicksort source.
Size of input file: 390,000,000
Counting lines ...
Lines encountered: 3,000,000
Longest line (including CR if present): 129
Allocated memory for pointers-to-lines in MB: 22
Assigning pointers ...
sizeof(int), sizeof(void*): 4, 4
Trying to allocate memory for the file itself in MB: 371 ... OK! Get on with fast internal accesses.
Uploading ...
Sorting 3,000,000 Pointers ...
Quicksort (Insertionsort for small blocks) commenced ...
| RightEnd: 000,001,500,225; NumberOfSplittings: 0,000,335,016; Done: 100% ...
NumberOfComparisons: 71,052,662
The time to sort 3,000,000 items via Quicksort+Insertionsort was 21,029 clocks.
Dumping the sorted data ...
- Done 100% ...
Dumped 3,000,000 lines.
OK! Incoming and resultant file's sizes match.
Dump time: 1,560 clocks.
Total time: 27,144 clocks.
Performance: 14,366 bytes/clock.
Done successfully.

E:\Sandokan_r3-+++\Sandokan_r3_vs_Windows-sort>sha1sum_Microsoft_V16_32bit_Ox.exe "QuickSortExternal_4+GB.txt"
a053faa74ffb6cad41e61e273a1a0e0049cb25e7  QuickSortExternal_4+GB.txt

E:\Sandokan_r3-+++\Sandokan_r3_vs_Windows-sort>timer sort /M 1048576 /R /T e: KT3million.txt /O KT3million.txt.Windows
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

Kernel Time  =     0.530 =    1%
User Time    =    28.610 =   96%
Process Time =    29.140 =   97%
Global Time  =    29.801 =  100%

E:\Sandokan_r3-+++\Sandokan_r3_vs_Windows-sort>sha1sum_Microsoft_V16_32bit_Ox.exe KT3million.txt.Windows
a053faa74ffb6cad41e61e273a1a0e0049cb25e7  KT3million.txt.Windows

Simply my proposal is to collect several such tools in one package, it will be very informative and much fun.

modified 28-Jun-14 14:40pm.

Having benchmarked Cubesort with Knight-Tours my amateurish evaluation is of two words: Mutsi! Mutsunka!

My Sandokan (r3fix) is inferior compared to Cubesort, 10,000,000 lines (128 bytes each) were sorted and after that sorted file was sorted once more:

------------------------------------------------------------------------------------------
| sorter \ filedataset | KT10000000.txt                      | KT10000000_SORTED.txt     |
------------------------------------------------------------------------------------------
| Cubesort             | 080 seconds                         | 045 seconds               |
| Windows' sort.exe    | 118 seconds                         | 115 seconds               |
| Sandokan             | 131 seconds; swappings: 36,826,242+ | 114 seconds; swappings: 0 |
------------------------------------------------------------------------------------------

The benchmark is downloadable at: www.sanmayce.com/Downloads/TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit.zip[^]

The full log follows:

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>dir
 Volume in drive E is SSD_Sanmayce
 Volume Serial Number is 9CF6-FEA3

 Directory of E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit

06/29/2014  11:45 PM    <DIR>          .
06/29/2014  11:45 PM    <DIR>          ..
06/29/2014  11:45 PM            12,566 cubesort-1.0_non-original.c
06/29/2014  11:45 PM            86,016 cubesort-1.0_non-original.exe
06/29/2014  11:45 PM           202,880 Cubesort.zip
06/29/2014  11:45 PM            24,490 Knight-tour_r8dump.c
06/29/2014  11:45 PM            79,872 Knight-tour_r8dump.exe
06/29/2014  11:45 PM               116 Make_EXEs.bat
06/29/2014  11:45 PM             1,604 MokujIN prompt.lnk
06/29/2014  11:45 PM           301,406 Sandokan_Logo.pdf
06/29/2014  11:45 PM           170,433 Sandokan_QuickSortExternal_4+GB_r3fix.c
06/29/2014  11:45 PM           122,368 Sandokan_QuickSortExternal_4+GB_r3fix.exe
06/29/2014  11:45 PM             6,144 timer64.exe
06/29/2014  11:45 PM             1,111 TriShowdown_Sandokan_vs_Windows_vs_Cubesort.bat
              12 File(s)      1,009,006 bytes
               2 Dir(s)  27,537,633,280 bytes free

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>move ..\KT10000000.txt
        1 file(s) moved.

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>TriShowdown_Sandokan_vs_Windows_vs_Cubesort.bat
Sorting 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe cubesort-1.0_non-original.exe KT10000000.txt
Cubesort: sorted 10000000 elements in 66503 clocks.

Kernel  Time =     6.754 =    8%
User    Time =    54.756 =   68%
Process Time =    61.511 =   76%    Virtual  Memory =   2676 MB
Global  Time =    80.355 =  100%    Physical Memory =   2447 MB
Sorting 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe sort /M 1048576 /T D: KT10000000.txt /O WindowsSORT_ResultantFile.txt

Kernel  Time =     1.466 =    1%
User    Time =    88.249 =   74%
Process Time =    89.716 =   75%    Virtual  Memory =   1028 MB
Global  Time =   118.248 =  100%    Physical Memory =   1021 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc Cubesort_ResultantFile.txt WindowsSORT_ResultantFile.txt /b
Comparing files Cubesort_ResultantFile.txt and WINDOWSSORT_RESULTANTFILE.TXT
FC: no differences encountered

Sorting 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe "Sandokan_QuickSortExternal_4+GB_r3fix.exe" KT10000000.txt /fast /ascend 512
Sandokan_QuickSortExternal_4+GB, revision 3fix, written by Kaze, using Bill Durango's Quicksort source.
Size of input file: 1,300,000,000
Counting lines ...
Lines encountered: 10,000,000
Longest line (including CR if present): 129
Allocated memory for pointers-to-lines in MB: 76
Assigning pointers ...
sizeof(int), sizeof(void*): 4, 8
Trying to allocate memory for the file itself in MB: 1239 ... OK! Get on with fast internal accesses.
Uploading ...
Sorting 10,000,000 Pointers ...
Quicksort (Insertionsort for small blocks) commenced ...
\ RightEnd: 000,001,500,225; NumberOfSplittings: 0,001,676,176; Done: 100% ...
NumberOfSwappings: 36,826,242
NumberOfComparisons: 255,105,484
The time to sort 10,000,000 items via Quicksort+Insertionsort was 106,704 clocks.
Dumping the sorted data ...
\ Done 100% ...
Dumped 10,000,000 lines.
OK! Incoming and resultant file's sizes match.
Dump time: 6,739 clocks.
Total time: 131,258 clocks.
Performance: 9,904 bytes/clock.
Done successfully.

Kernel  Time =     5.397 =    4%
User    Time =   116.173 =   88%
Process Time =   121.571 =   92%    Virtual  Memory =   1320 MB
Global  Time =   131.461 =  100%    Physical Memory =   1321 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc QuickSortExternal_4+GB.txt WindowsSORT_ResultantFile.txt /b
Comparing files QuickSortExternal_4+GB.txt and WINDOWSSORT_RESULTANTFILE.TXT
FC: no differences encountered

Sorting sorted 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe cubesort-1.0_non-original.exe WindowsSORT_ResultantFile.txt
Cubesort: sorted 10000000 elements in 28064 clocks.

Kernel  Time =     6.723 =   14%
User    Time =    27.284 =   60%
Process Time =    34.008 =   74%    Virtual  Memory =   2661 MB
Global  Time =    45.474 =  100%    Physical Memory =   2560 MB
Sorting sorted 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe sort /M 1048576 /T D: WindowsSORT_ResultantFile.txt /O WindowsSORT_ResultantFile_.txt

Kernel  Time =     1.170 =    1%
User    Time =    76.237 =   66%
Process Time =    77.407 =   67%    Virtual  Memory =   1028 MB
Global  Time =   115.081 =  100%    Physical Memory =   1021 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc Cubesort_ResultantFile.txt WindowsSORT_ResultantFile_.txt /b
Comparing files Cubesort_ResultantFile.txt and WINDOWSSORT_RESULTANTFILE_.TXT
FC: no differences encountered

Sorting sorted 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe "Sandokan_QuickSortExternal_4+GB_r3fix.exe" WindowsSORT_ResultantFile.txt /fast /ascend 512
Sandokan_QuickSortExternal_4+GB, revision 3fix, written by Kaze, using Bill Durango's Quicksort source.
Size of input file: 1,300,000,000
Counting lines ...
Lines encountered: 10,000,000
Longest line (including CR if present): 129
Allocated memory for pointers-to-lines in MB: 76
Assigning pointers ...
sizeof(int), sizeof(void*): 4, 8
Trying to allocate memory for the file itself in MB: 1239 ... OK! Get on with fast internal accesses.
Uploading ...
Sorting 10,000,000 Pointers ...
Quicksort (Insertionsort for small blocks) commenced ...
\ RightEnd: 000,010,000,000; NumberOfSplittings: 0,001,611,392; Done: 100% ...
NumberOfSwappings: 0
NumberOfComparisons: 214,016,797
The time to sort 10,000,000 items via Quicksort+Insertionsort was 90,278 clocks.
Dumping the sorted data ...
\ Done 100% ...
Dumped 10,000,000 lines.
OK! Incoming and resultant file's sizes match.
Dump time: 5,429 clocks.
Total time: 114,488 clocks.
Performance: 11,354 bytes/clock.
Done successfully.

Kernel  Time =     6.364 =    5%
User    Time =    99.372 =   86%
Process Time =   105.737 =   92%    Virtual  Memory =   1320 MB
Global  Time =   114.691 =  100%    Physical Memory =   1321 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc QuickSortExternal_4+GB.txt WindowsSORT_ResultantFile_.txt /b
Comparing files QuickSortExternal_4+GB.txt and WINDOWSSORT_RESULTANTFILE_.TXT
FC: no differences encountered

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>

Cubesort is one lovely piece of software, Mr. Hoven I salute you with Beth Ditto's Heavy Cross[^]:

It's a cruel cruel world to face on your own
A heavy cross to carry alone
The lights are on but everyone's gone
And it's cruel
It's a funny way to make ends meet
When the lights are out on every street
It feels alright but never complete
without you
I chose you
If it's already have been done
Undo it
It takes two
It is up to me and you to proove it
On the rainy nights even the coldest days
you're moments ago but seconds away
The principle of Nature it's true but it's a cruel world
See we can play it safe or play it cool
Follow the leader or make up all the rules
Whatever you want the choice is yours
So choose me
I chose you

"If it's already have been done... undo it." - I wish Beth was into programming.

The most decent Quicksort I know is this:
https://code.google.com/p/libdivsufsort/[^]

Cubesort is awesome, with big potential on top of that.
The thing that impresses me most is its construction speed, not to mention the 'free' dump.

Couldn't resist not to try my 'secret weapon' - a frozen/unfinished sub-project called 'Tcheburaschkasort'.
It is entirely based on the titaniumESQUEly strong Bayer-McCreight algorithm which I implemented specifically and only as order 3 (three children maximum).
It's been some time since I wrote it, enough to forget this-and-that, but the initial idea was to use next dimension i.e. to use millions of B-trees.

My unfinished Tcheburaschkasort currently uses 24bit pseudo-hash (in fact first 1|2|3 byte(s) ARE a slot) giving a forest of 16,777,216 B-Trees of order 3:

UINT PseudoHash(const char *str, unsigned int wrdlen)
{
	UINT hash32 = 0;
	const char *p = str;
	// Use 256-based system for first 3 bytes i.e. left is more significant:
	// Currently 3bytes long i.e. 24bit:
	if (wrdlen>=1) {
		hash32 =  hash32 | ((*p)<<16);
		p += 1;
	}
	if (wrdlen>=2) {
		hash32 =  hash32 | ((*p)<<8);
		p += 1;
	}
	if (wrdlen>=3) {
		hash32 =  hash32 | ((*p)<<0);
		p += 1;
	}
	return hash32;
}

Each slot houses the root of a tree.
Not using any hash Tcheburaschkasort resembles a hypercube of order 0, using hash makes it 1D i.e. of order 1 - lookup hashtable is the axis.

Blah-blah, in short the randomness of those prefixes (1..3bytes long) decides the speed performance.
In example with KT10000000.txt all first 3 bytes are equal, 'A8C', so there is one only tree and performance is poor.
Because all the 10,000,000 lines start from board position A8.
Knight-tours: each square represents a board position, as A1(bottom-left), H8(top-right):

-----------------
|a8 |b8 |...|h8 |
-----------------
|a7 |...|       |
-----------------
|...|...|       |
-----------------
|a1 |...|...|h1 |
-----------------

When making the data more diverse, e.g. reverse the order of tours then for KT10000000.txt we will have 50 trees, see below.
Let us see what boost comes from this diversity.

So, Tcheburaschkasort vs Cubesort results for KT10M filedataset (10,000,000 Knight-Tours from A8, reversed):

NOTE:
Tcheburaschkasort is based on my superfast multi-purpose text ripper Leprechaun.
Tcheburaschkasort still DOES NOT make in-order dump/traversal, resultant file is unsorted, to be done. This DOES NOT affect results, though.

The full log is as follows:

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>dir
 Volume in drive E is SSD_Sanmayce
 Volume Serial Number is 9CF6-FEA3

 Directory of E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit

07/03/2014  04:19 AM    <DIR>          .
07/03/2014  04:19 AM    <DIR>          ..
07/03/2014  04:20 AM               823 BiShowdown_Cubesort_Tcheburaschkasort.bat
07/03/2014  04:20 AM            12,566 cubesort-1.0_non-original.c
07/03/2014  04:20 AM            86,016 cubesort-1.0_non-original.exe
07/03/2014  04:20 AM           202,880 Cubesort.zip
07/03/2014  04:20 AM            24,490 Knight-tour_r8dump.c
07/03/2014  04:20 AM            79,872 Knight-tour_r8dump.exe
07/03/2014  04:20 AM            25,071 Knight-tour_r8dump_REVERSE.c
07/03/2014  04:20 AM            79,360 Knight-tour_r8dump_REVERSE.exe
07/03/2014  04:20 AM               216 Make_EXEs.bat
07/03/2014  04:20 AM             1,604 MokujIN prompt.lnk
07/03/2014  04:20 AM           170,433 Sandokan_QuickSortExternal_4+GB_r3fix.c
07/03/2014  04:20 AM           122,368 Sandokan_QuickSortExternal_4+GB_r3fix.exe
07/03/2014  04:20 AM           327,819 TcheburaschkaSort.c
07/03/2014  04:20 AM         1,771,134 TcheburaschkaSort.cod
07/03/2014  04:20 AM           140,288 TcheburaschkaSort.exe
07/03/2014  04:20 AM             6,144 timer64.exe
              16 File(s)      3,051,084 bytes
               2 Dir(s)  29,523,390,464 bytes free

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>BiShowdown_Cubesort_Tcheburaschkasort.bat
Dumping 10,000,000 reversed KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>Knight-tour_r8dump_REVERSE A8 10000000 1>KT10000000_from-end-to-start.txt

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>sort /M 1048576 /T D: /R KT10000000_from-end-to-start.txt /O KT10000000_from-end-to-start-SORTED-IN-REVERSE.txt
Sorting 10,000,000 KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe cubesort-1.0_non-original.exe KT10000000_from-end-to-start.txt
Cubesort: sorted 10000000 elements in 94349 clocks.

Kernel  Time =     8.283 =    7%
User    Time =    59.592 =   55%
Process Time =    67.876 =   62%    Virtual  Memory =   2689 MB
Global  Time =   108.217 =  100%    Physical Memory =   2497 MB
Sorting 10,000,000 KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe sort /M 1048576 /T D: KT10000000_from-end-to-start.txt /O KT10000000_from-end-to-start-SORTED.txt

Kernel  Time =     1.778 =    1%
User    Time =    83.132 =   48%
Process Time =    84.911 =   49%    Virtual  Memory =   1028 MB
Global  Time =   173.113 =  100%    Physical Memory =   1021 MB

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>fc Cubesort_ResultantFile.txt KT10000000_from-end-to-start-SORTED.txt /b
Comparing files Cubesort_ResultantFile.txt and KT10000000_FROM-END-TO-START-SORTED.TXT
FC: no differences encountered

Sorting 10,000,000 KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>dir KT10000000_from-end-to-start.txt/b 1>TcheburaschkaSort.lst

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe TcheburaschkaSort TcheburaschkaSort.lst TcheburaschkaSort.txt 2900123 y
Leprechaun_singleton (Fast-In-Future Greedy n-gram-Ripper), rev. 16FIXFIX, written by Svalqyatchx.
Purpose: Rips all distinct 1-grams (1-word phrases) with length 1..128 chars from incoming texts.
Feature1: All words within x-lets/n-grams are in range 1..31 chars inclusive.
Feature2: In this revision 128MB 1-way hash is used which results in 16,777,216 external B-Trees of order 3.
Feature3: In this revision, 1 pass is to be made.
Feature4: If the external memory has latency 99+microseconds then !(look no further), IOPS(seek-time) rules.
Pass #1 of 1:
Size of input file with files for Leprechauning: 34
Allocating HASH memory 134,217,793 bytes ... OK
Allocating memory 2833MB ... OK
Size of Input TEXTual file: 1,300,000,000
\; 00,222,222P/s; Phrase count: 10,000,000 of them 10,000,000 distinct; Done: 64/64
Bytes per second performance: 28,888,888B/s
Phrases per second performance: 222,222P/s
Time for putting phrases into trees: 45 second(s)
Flushing UNsorted phrases: 100%; Shaking trees performance: 00,952,380P/s
Time for shaking phrases from trees: 21 second(s)
Leprechaun: Current pass done.

Total memory needed for one pass: 2,133,638KB
Total distinct phrases: 10,000,000
Total time: 67 second(s)
Total performance: 149,253P/s i.e. phrases per second
Leprechaun: Done.

Kernel  Time =     6.193 =    9%
User    Time =    59.732 =   89%
Process Time =    65.926 =   99%    Virtual  Memory =   2967 MB
Global  Time =    66.580 =  100%    Physical Memory =   2218 MB

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>type Leprechaun.LOG
Leprechaun report:
Number Of Hash Collisions(Distinct WORDs - Number Of Trees): 9,999,950
Number Of Trees(GREATER THE BETTER): 50
Number Of LEAFs(littler THE BETTER) not counting ROOT LEAFs: 7,533,898
Highest Tree not counting ROOT Level i.e. CORONA levels(littler THE BETTER): 15
Used value for third parameter in KB: 2,900,123
Use next time as third parameter: 2,133,638
Total Attempts to Find/Put WORDs into B-trees order 3: 164,504,421

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>type KT10000000_from-end-to-start.txt|more
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
F6E4C3D1E3D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3A4B6D5F6E4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
B6A4C3D1E3D5F6E4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5F4E6C5D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
F6E4C3D1E3D5F4E6C5D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3D5F6E4C5E6F4D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
C3D1E3D5F6E4C5E6F4D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
F6D5E3D1C3E4C5E6F4D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
...

Oh, and for those who are interested here are the stats (memory requirement and number of attempts i.e. depthness of the B-tree):
Simply you need 15 (in worst case) attempts in order to find a key within 10,000,000 keys.
Nothing impressive, 15 tries, yet with no unpleasant surprises like unbalancing.
Also for data 1,240MB (the 130x10,000,000) the tree is 2,133,638KB=2,083MB in size.

There are three reasons for Tcheburaschkasort's poor performance, first is the slow dumping of sorted data:
66 seconds are divided in:
Sorting: Time for putting phrases into trees: 45 second(s)
Dumping: Time for shaking phrases from trees: 21 second(s)

Second is the way I insert new keys, for speed boost (when incoming data is not of unique keys as here) fast-search is performed and if failed new search-insert is enforced, grmbl.
In simple words, insertion is slow, especially for order 3, double-grmbl.

Third is the parsing of keys, in Cubesort I wrote it synthetically:

fread(&z_array[cnt].key, sizeof(keyType), 1, ifp);

While in Tcheburaschkasort the parsing is byte-by-byte, as in real-world rippers:

                if ( workbyte < '0' ) // Most characters are under alphabet - only one if // Cheburashka
                {
ElStupido:
                        // This fragment is MIRRORed: #1 copy [
                        if (workbyte == 10) {NumberOfLines++;}
...
// Cheburashka [ 
                else if( workbyte <= '9' )
		{
                        //if( wrdlen < 31 )
                        if( wrdlen < 128 ) // Cheburashka
                        //if( wrdlen < LongestLineInclusive )
                        { wrd[ wrdlen ] = workbyte; }
                        wrdlen++;
		}
                else if( workbyte >= 'A' &&  workbyte <= 'Z' )
		{
                        //if( wrdlen < 31 )
                        if( wrdlen < 128 ) // Cheburashka
                        //if( wrdlen < LongestLineInclusive )
                        { wrd[ wrdlen ] = workbyte; }
                        wrdlen++;
		}
// Cheburashka ]
                else if( workbyte >= 'a' &&  workbyte <= 'z' )
		{
                        //if( wrdlen < 31 )
                        if( wrdlen < 128 ) // Cheburashka
                        //if( wrdlen < LongestLineInclusive )
                        { wrd[ wrdlen ] = workbyte; }
                        wrdlen++;
		}
		else
                {
                        // This fragment is MIRRORed: #2 copy [
                goto ElStupido;
                        // This fragment is MIRRORed: #2 copy ]
		}

Scared! Well above fragment handles 'words' of alpha-numerical type 1..128 bytes in length.

Having an old Samsung 470 SSD on my laptop (Core 2 T7500 2200MHz) I ran the scariest sort of all, with all-external memory operations i.e. no physical no virtual used:

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe TcheburaschkaSort TcheburaschkaSort.lst TcheburaschkaSort.txt 2900123 z
Leprechaun_singleton (Fast-In-Future Greedy n-gram-Ripper), rev. 16FIXFIX, written by Svalqyatchx.
Purpose: Rips all distinct 1-grams (1-word phrases) with length 1..128 chars from incoming texts.
Feature1: All words within x-lets/n-grams are in range 1..31 chars inclusive.
Feature2: In this revision 128MB 1-way hash is used which results in 16,777,216 external B-Trees of order 3.
Feature3: In this revision, 1 pass is to be made.
Feature4: If the external memory has latency 99+microseconds then !(look no further), IOPS(seek-time) rules.
Pass #1 of 1:
Size of input file with files for Leprechauning: 34
Allocating HASH memory 134,217,793 bytes ... OK
Allocating/ZEROing 2,969,725,966 bytes swap file ... OK
Size of Input TEXTual file: 1,300,000,000
\; 00,008,643P/s; Phrase count: 10,000,000 of them 10,000,000 distinct; Done: 64/64
Bytes per second performance: 1,123,595B/s
Phrases per second performance: 8,643P/s
Time for putting phrases into trees: 1157 second(s)
Flushing UNsorted phrases: 100%; Shaking trees performance: 00,056,179P/s
Time for shaking phrases from trees: 356 second(s)
Leprechaun: Current pass done.

Total memory needed for one pass: 2,133,638KB
Total distinct phrases: 10,000,000
Total time: 1528 second(s)
Total performance: 6,544P/s i.e. phrases per second
Leprechaun: Done.

Kernel  Time =  1096.609 =   71%
User    Time =   217.449 =   14%
Process Time =  1314.058 =   86%    Virtual  Memory =    130 MB
Global  Time =  1527.601 =  100%    Physical Memory =    131 MB

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>

Only 1527/108=14 times slower than Cubesort, not bad in my eyes.

As for Tcheburaschka, few things remain to be done, in-order traversal dump and few more raw ideas, however I lost my momentum, now I am interested in textual decompression.

Ah, and the name, Чебурашка, it is a little supercalm soullet (English lacks double diminutives), in fact the golden Russian animatronics movie, love it.

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.