/gridsort

A stable adaptive partitioning comparison sort.

Primary LanguageCThe UnlicenseUnlicense

Intro

This document describes a partitioning stable adaptive comparison-based sort named gridsort.

Binary Cube

Gridsort sorts data by storing data in a simplified binary cube, a multidimentional sorted array. The binary cube offers excellent cache utilization. It's easiest to view a binary cube as a hash table, but instead of a hash function to find a bucket it uses a binary search on a lookup table.

Boundless Binary Search

The first step when sorting an element is a boundless binary search to pin point the bucket where the element should be stored. A boundless binary search is up to two times faster than the legacy binary search used by most applications. Once a bucket is found the element is added to the end of the bucket.

Gridsort switches to an adaptive binary search when it detects data that is already sorted.

Quadsort

Once a bucket overflows it is sorted using quadsort and a new bucket is created. The sorted data is split between the two buckets so each bucket is half full. The lowest element in each bucket is added to the lookup table.

Finish

Once all elements have been inserted into the binary cube every bucket receives a final sort and is copied back to the original array.

Memory

Gridsort allocates 2 * sqrt(n) blocks of memory of sqrt(n) size.

Data Types

The C implementation of gridsort supports long doubles and 8, 16, 32, and 64 bit data types. By using pointers it's possible to sort any other data type.

Interface

Gridsort uses the same interface as qsort, which is described in man qsort.

Big O

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

Gridsort makes n comparisons when the data is fully in order or in reverse order.

Porting

People wanting to port gridsort might want to have a look at twinsort, which is a simplified implementation of quadsort. Gridsort itself is a simplified implementation of cubesort. Another sort worth looking at is fluxsort which uses simpler top-down partitioning instead of gridsort's bottom-up partitioning.

Visualization

In the visualization below eight tests are performed. Random, Ascending, Ascending Saw, Generic, Descending, Descending Saw, Random Tail, and Wave order.

cubesort visualization

In the visualization below one test is performed on a random distribution. This visualization more accurately shows the use of pointer operations to partition memory.

Cyan numbers are unsorted, green numbers are sorted, white numbers are sorted and ready to be merged, yellow numbers are the index upon which a binary search is performed to find out where to insert the next number, magenta numbers are ready to be merged back to the main array.

gridsort visualization

Benchmarks

The following benchmark was on WSL gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04) using the wolfsort benchmark. The source code was compiled using g++ -O3 -w -fpermissive bench.c. The bar graph shows the best run out of 10 on 32 bit integers. Comparisons for gridsort and std::stable_sort are inlined.

gridsort vs stdsort

data table
Name Items Type Best Average Loops Samples Distribution
stablesort 1000000 128 0.141087 0.142480 1 10 random order
gridsort 1000000 128 0.101785 0.103576 1 10 random order
Name Items Type Best Average Loops Samples Distribution
stablesort 1000000 64 0.076895 0.077535 1 10 random order
gridsort 1000000 64 0.051316 0.051824 1 10 random order
Name Items Type Best Average Loops Samples Distribution
stablesort 1000000 32 0.072891 0.073191 1 10 random order
gridsort 1000000 32 0.050891 0.051147 1 10 random order
stablesort 1000000 32 0.010608 0.010848 1 10 ascending order
gridsort 1000000 32 0.003287 0.003543 1 10 ascending order
stablesort 1000000 32 0.017488 0.017697 1 10 ascending saw
gridsort 1000000 32 0.012015 0.012160 1 10 ascending saw
stablesort 1000000 32 0.041584 0.041741 1 10 generic order
gridsort 1000000 32 0.015809 0.016224 1 10 generic order
stablesort 1000000 32 0.010641 0.010863 1 10 descending order
gridsort 1000000 32 0.003577 0.003620 1 10 descending order
stablesort 1000000 32 0.014260 0.014466 1 10 descending saw
gridsort 1000000 32 0.009878 0.010047 1 10 descending saw
stablesort 1000000 32 0.026343 0.026791 1 10 random tail
gridsort 1000000 32 0.015311 0.015351 1 10 random tail
stablesort 1000000 32 0.043529 0.043730 1 10 random half
gridsort 1000000 32 0.028233 0.028463 1 10 random half
stablesort 1000000 32 0.013824 0.013961 1 10 ascending tiles
gridsort 1000000 32 0.012287 0.012459 1 10 ascending tiles

The following benchmark was on WSL gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). The source code was compiled using gcc -O3 bench.c. The bar graph shows the best run out of 100 on 32 bit integers. Comparisons for gridsort and qsort are not inlined. The stdlib qsort() in the benchmark is a mergesort variant.

gridsort vs stdsort

data table
Name Items Type Best Average Compares Samples Distribution
qsort 100000 128 0.019117 0.019996 1536181 100 random order
gridsort 100000 128 0.012686 0.012730 1639247 100 random order
Name Items Type Best Average Compares Samples Distribution
qsort 100000 32 0.008465 0.008580 1536634 100 random order
gridsort 100000 32 0.006045 0.006135 1643169 100 random order
qsort 100000 32 0.002019 0.002113 815024 100 ascending order
gridsort 100000 32 0.000656 0.000669 202740 100 ascending order
qsort 100000 32 0.002818 0.002827 915019 100 ascending saw
gridsort 100000 32 0.001976 0.001994 582000 100 ascending saw
qsort 100000 32 0.006402 0.006545 1532339 100 generic order
gridsort 100000 32 0.002793 0.002948 1146648 100 generic order
qsort 100000 32 0.002450 0.002566 853904 100 descending order
gridsort 100000 32 0.000661 0.000668 200034 100 descending order
qsort 100000 32 0.002827 0.002941 1063907 100 descending saw
gridsort 100000 32 0.001666 0.001737 771299 100 descending saw
qsort 100000 32 0.003734 0.003943 1012028 100 random tail
gridsort 100000 32 0.002057 0.002142 625065 100 random tail
qsort 100000 32 0.005442 0.005595 1200835 100 random half
gridsort 100000 32 0.003511 0.003573 998798 100 random half
qsort 100000 32 0.004080 0.004179 1209200 100 ascending tiles
gridsort 100000 32 0.003189 0.003343 868332 100 ascending tiles