Awesome

Origin

Octosort is a block merge sort based on WikiSort and quadsort. This document primarily lists notable differences and some benchmarks.

Octo swap

Like quadsort has the quad swap, octosort has the octo swap. The swap sorts between 4 and 8 elements at a time and performs runs on reverse ordered data.

Monobound binary search

WikiSort's binary search has been replaced with a monobound binary search, which is up to two times faster.

Gries-Mills rotation

WikiSort's triple reversal rotation has been replaced with a Gries-Mills rotation, which is up to two times faster.

Quad merge

WikiSort already implemented a quad merge, which has been updated to no longer detect reverse order runs, since that's taken care off by the octo swap.

Tail merge

Quadsort's tail merge routine was added to perform partially in-place merges.

Data Types

Support was added for long doubles and 8, 16, 32, and 64 bit data types. By using 32 or 64 bit pointers it's possible to sort any other data type.

Interface

The interface was changed to use the same one as qsort, which is described in man qsort.

Memory

By default octosort uses 512 elements worth of stack memory.

The minimum memory requirement for octosort is 1 element of stack memory, it can be configured to use n / 2 memory.

Big O

                 ┌───────────────────────┐┌───────────────────────┐
                 │comparisons            ││swap memory            │
┌───────────────┐├───────┬───────┬───────┤├───────┬───────┬───────┤┌──────┐┌─────────┐┌─────────┐
│name           ││min    │avg    │max    ││min    │avg    │max    ││stable││partition││adaptive │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│mergesort      ││n log n│n log n│n log n││n      │n      │n      ││yes   ││no       ││no       │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│octosort       ││n      │n log n│n log n││1      │1      │1      ││yes   ││no       ││yes      │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│quicksort      ││n      │n log n│n²     ││1      │1      │1      ││no    ││yes      ││no       │
└───────────────┘└───────┴───────┴───────┘└───────┴───────┴───────┘└──────┘└─────────┘└─────────┘

Benchmarks

The following benchmark was on WSL 2 gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04). The source code was compiled using gcc -O3 bench.c. Each test was ran 100 times and only the best run is reported. It's generated by running the benchmark using 100000 100 as the argument.

Graph

<details><summary><b>data table</b></summary>

Name	Items	Type	Best	Average	Compares	Samples	Distribution
qsort	100000	32	0.008508	0.008779	1536367	100	random order
octosort	100000	32	0.008792	0.008889	1800800	100	random order

qsort	100000	32	0.002024	0.002225	815024	100	ascending order
octosort	100000	32	0.000328	0.000345	116524	100	ascending order

qsort	100000	32	0.002831	0.003088	915020	100	ascending saw
octosort	100000	32	0.001537	0.001565	370372	100	ascending saw

qsort	100000	32	0.006426	0.006722	1531997	100	generic order
octosort	100000	32	0.006437	0.006515	1633855	100	generic order

qsort	100000	32	0.002456	0.002657	853904	100	descending order
octosort	100000	32	0.000221	0.000227	99999	100	descending order

qsort	100000	32	0.002832	0.003001	1063907	100	descending saw
octosort	100000	32	0.001738	0.001849	693171	100	descending saw

qsort	100000	32	0.003744	0.003939	1012256	100	random tail
octosort	100000	32	0.002684	0.002740	630603	100	random tail

qsort	100000	32	0.005464	0.005732	1200738	100	random half
octosort	100000	32	0.004859	0.004911	1022394	100	random half

qsort	100000	32	0.004147	0.004685	1209200	100	ascending tiles
octosort	100000	32	0.003146	0.003437	790377	100	ascending tiles

</details>

The following benchmark was generated using 1000000 0 0 as the argument.

Graph

<details><summary><b>data table</b></summary>

Name	Items	Type	Best	Average	Compares	Samples	Distribution
qsort	4	32	0.001369	0.001439	5	100	random 4
octosort	4	32	0.000765	0.000776	6	100	random 4

qsort	8	32	0.001511	0.001555	17	100	random 8
octosort	8	32	0.000893	0.000939	19	100	random 8

qsort	16	32	0.001587	0.001952	46	100	random 16
octosort	16	32	0.001221	0.001281	55	100	random 16

qsort	32	32	0.001795	0.002612	121	100	random 32
octosort	32	32	0.001319	0.001602	124	100	random 32

qsort	64	32	0.002037	0.003018	309	100	random 64
octosort	64	32	0.001492	0.002195	319	100	random 64

qsort	128	32	0.002304	0.003754	745	100	random 128
octosort	128	32	0.001674	0.003189	775	100	random 128

qsort	256	32	0.003293	0.005024	1738	100	random 256
octosort	256	32	0.001909	0.003613	1806	100	random 256

qsort	512	32	0.005293	0.006220	3968	100	random 512
octosort	512	32	0.003113	0.005086	4112	100	random 512

qsort	1024	32	0.006530	0.007128	8962	100	random 1024
octosort	1024	32	0.005290	0.006494	10031	100	random 1024

qsort	2048	32	0.007341	0.007810	19962	100	random 2048
octosort	2048	32	0.006943	0.007444	22885	100	random 2048

qsort	4096	32	0.008086	0.008499	43966	100	random 4096
octosort	4096	32	0.008295	0.008441	51035	100	random 4096

qsort	8192	32	0.008740	0.009142	96149	100	random 8192
octosort	8192	32	0.009122	0.009198	112238	100	random 8192

qsort	16384	32	0.009405	0.009830	208702	100	random 16384
octosort	16384	32	0.009827	0.009949	244511	100	random 16384

qsort	32768	32	0.010039	0.010421	450105	100	random 32768
octosort	32768	32	0.010525	0.010680	529041	100	random 32768

qsort	65536	32	0.010708	0.011123	965773	100	random 65536
octosort	65536	32	0.011250	0.011431	1138363	100	random 65536

qsort	131072	32	0.011316	0.011698	2062601	100	random 131072
octosort	131072	32	0.011982	0.012159	2437514	100	random 131072

</details>