/octosort

Octosort is an in-place stable adaptive block merge sort.

Primary LanguageC

Origin

Octosort is 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. Octosort can be configured to use n / 2 memory with a fallback to the stack.

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

data table
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

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

Graph

data table
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