百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
C

crumsort

> 编程语言
开源

一种无分支的不稳定快速排序/归并排序,具有高度的自适应性。

336 stars0 点赞0 次浏览
访问官网GitHub

工具介绍

一种无分支的不稳定快速排序/归并排序,具有高度的自适应性。

Intro

This document describes a hybrid quicksort / mergesort named crumsort. The sort is in-place, unstable, adaptive, branchless, and has exceptional performance.

Analyzer

Crumsort starts out with an analyzer that sorts fully in-order or reverse-order arrays using n comparisons. It also obtains a measure of presortedness for 4 segments of the array and switches to quadsort if a segment is more than 50% ordered.

Partitioning

Partitioning is performed in a top-down manner similar to quicksort. Crumsort obtains the pseudomedian of 9 for partitions smaller than 2048 elements, and the median of 16 for paritions smaller than 65536. For larger partitions crumsort obtains the median of 128, 256, or 512 as an approximation of the cubic root of the partition size. While the square root is optimal in theory, the law of diminishing returns appears to apply to increasing the number of pivot candidates. Hardware limitations need to be factored in as well.

For large partitions crumsort will swap 128-512 random elements to the start of the array, sort them with quadsort, and take the center right element. Using pseudomedian instead of median selection on large arrays is slower, likely due to cache pollution.

The median element obtained will be referred to as the pivot. Partitions that grow smaller than 24 elements are sorted with quadsort.

Fulcrum Partition

After obtaining a pivot the array is parsed from start to end using the fulcrum partitioning scheme. The scheme is similar to the original quicksort scheme known as the Hoare partition with some notable differences. The differences are perhaps best explained with two code examples.

c
int hoare_partition(int array[], int head, int tail)
{
        int pivot = head++;
        int swap;

        while (1)
        {
                while (array[head]  array[pivot])
                {
                        tail--;
                }

                if (head >= tail)
                {
                        swap = array[pivot]; array[pivot] = array[tail]; array[tail] = swap;

                        return tail;
                }
                swap = array[head]; array[head] = array[tail]; array[tail] = swap;
        }
}
c
int fulcrum_partition(int array[], int head, int tail)
{
        int pivot = array[head];

        while (1)
        {
                if (array[tail] > pivot)
                {
                        tail--;
                        continue;
                }

                if (head >= tail)
                {
                        array[head] = pivot;
                        return head;
                }
                array[head++] = array[tail];

                while (1)
                {
                        if (head >= tail)
                        {
                                array[head] = pivot;
                                return head;
                        }

                        if (array[head] data table

|      Name |    Items | Type |     Best |  Average |  Compares | Samples |     Distribution |
| --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- |
|   pdqsort |   100000 |  128 | 0.005908 | 0.005975 |         0 |     100 |     random order |
|  crumsort |   100000 |  128 | 0.008262 | 0.008316 |         0 |     100 |     random order |
|  fluxsort |   100000 |  128 | 0.008567 | 0.008676 |         0 |     100 |     random order |

|      Name |    Items | Type |     Best |  Average |  Compares | Samples |     Distribution |
| --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- |
|   pdqsort |   100000 |   64 | 0.002645 | 0.002668 |         0 |     100 |     random order |
|  crumsort |   100000 |   64 | 0.001896 | 0.001927 |         0 |     100 |     random order |
|  fluxsort |   100000 |   64 | 0.001942 | 0.001965 |         0 |     100 |     random order |

|      Name |    Items | Type |     Best |  Average |     Loops | Samples |     Distribution |
| --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- |
|   pdqsort |   100000 |   32 | 0.002682 | 0.002705 |         0 |     100 |     random order |
|  crumsort |   100000 |   32 | 0.001797 | 0.001812 |         0 |     100 |     random order |
|  fluxsort |   100000 |   32 | 0.001834 | 0.001858 |         0 |     100 |     random order |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.000801 | 0.000807 |         0 |     100 |     random % 100 |
|  crumsort |   100000 |   32 | 0.000560 | 0.000575 |         0 |     100 |     random % 100 |
|  fluxsort |   100000 |   32 | 0.000657 | 0.000670 |         0 |     100 |     random % 100 |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.000098 | 0.000099 |         0 |     100 |  ascending order |
|  crumsort |   100000 |   32 | 0.000043 | 0.000046 |         0 |     100 |  ascending order |
|  fluxsort |   100000 |   32 | 0.000044 | 0.000044 |         0 |     100 |  ascending order |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.003460 | 0.003483 |         0 |     100 |    ascending saw |
|  crumsort |   100000 |   32 | 0.000628 | 0.000638 |         0 |     100 |    ascending saw |
|  fluxsort |   100000 |   32 | 0.000328 | 0.000336 |         0 |     100 |    ascending saw |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.002828 | 0.002850 |         0 |     100 |       pipe organ |
|  crumsort |   100000 |   32 | 0.000359 | 0.000363 |         0 |     100 |       pipe organ |
|  fluxsort |   100000 |   32 | 0.000215 | 0.000219 |         0 |     100 |       pipe organ |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.000201 | 0.000203 |         0 |     100 | descending order |
|  crumsort |   100000 |   32 | 0.000055 | 0.000055 |         0 |     100 | descending order |
|  fluxsort |   100000 |   32 | 0.000055 | 0.000056 |         0 |     100 | descending order |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.003229 | 0.003260 |         0 |     100 |   descending saw |
|  crumsort |   100000 |   32 | 0.000637 | 0.000645 |         0 |     100 |   descending saw |
|  fluxsort |   100000 |   32 | 0.000328 | 0.000332 |         0 |     100 |   descending saw |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.002558 | 0.002579 |         0 |     100 |      random tail |
|  crumsort |   100000 |   32 | 0.000879 | 0.000895 |         0 |     100 |      random tail |
|  fluxsort |   100000 |   32 | 0.000626 | 0.000631 |         0 |     100 |      random tail |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.002660 | 0.002677 |         0 |     100 |      random half |
|  crumsort |   100000 |   32 | 0.001200 | 0.001207 |         0 |     100 |      random half |
|  fluxsort |   100000 |   32 | 0.001069 | 0.001084 |         0 |     100 |      random half |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.002310 | 0.002328 |         0 |     100 |  ascending tiles |
|  crumsort |   100000 |   32 | 0.001520 | 0.001534 |         0 |     100 |  ascending tiles |
|  fluxsort |   100000 |   32 | 0.000294 | 0.000298 |         0 |     100 |  ascending tiles |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.002659 | 0.002681 |         0 |     100 |     bit reversal |
|  crumsort |   100000 |   32 | 0.001787 | 0.001800 |         0 |     100 |     bit reversal |
|  fluxsort |   100000 |   32 | 0.001696 | 0.001721 |         0 |     100 |     bit reversal |

data table

|      Name |    Items | Type |     Best |  Average |  Compares | Samples |     Distribution |
| --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- |
|   pdqsort |       10 |   32 | 0.087140 | 0.087436 |       0.0 |      10 |        random 10 |
|  crumsort |       10 |   32 | 0.049921 | 0.050132 |       0.0 |      10 |        random 10 |
|  fluxsort |       10 |   32 | 0.048499 | 0.048724 |       0.0 |      10 |        random 10 |
|           |          |      |          |          |           |         |                  |
|   pdqsort |      100 |   32 | 0.169583 | 0.169940 |       0.0 |      10 |       random 100 |
|  crumsort |      100 |   32 | 0.113443 | 0.113882 |       0.0 |      10 |       random 100 |
|  fluxsort |      100 |   32 | 0.113426 | 0.113955 |       0.0 |      10 |       random 100 |
|           |          |      |          |          |           |         |                  |
|   pdqsort |     1000 |   32 | 0.207200 | 0.207858 |       0.0 |      10 |      random 1000 |
|  crumsort |     1000 |   32 | 0.135912 | 0.136251 |       0.0 |      10 |      random 1000 |
|  fluxsort |     1000 |   32 | 0.137019 | 0.138586 |       0.0 |      10 |      random 1000 |
|           |          |      |          |          |           |         |                  |
|   pdqsort |    10000 |   32 | 0.238297 | 0.239006 |       0.0 |      10 |     random 10000 |
|  crumsort |    10000 |   32 | 0.158249 | 0.158476 |       0.0 |      10 |     random 10000 |
|  fluxsort |    10000 |   32 | 0.158445 | 0.158694 |       0.0 |      10 |     random 10000 |
|           |          |      |          |          |           |         |                  |
|   pdqsort |   100000 |   32 | 0.270447 | 0.270855 |       0.0 |      10 |    random 100000 |
|  crumsort |   100000 |   32 | 0.181770 | 0.183123 |       0.0 |      10 |    random 100000 |
|  fluxsort |   100000 |   32 | 0.185907 | 0.186829 |       0.0 |      10 |    random 100000 |
|           |          |      |          |          |           |         |                  |
|   pdqsort |  1000000 |   32 | 0.303525 | 0.305467 |       0.0 |      10 |   random 1000000 |
|  crumsort |  1000000 |   32 | 0.206979 | 0.208153 |       0.0 |      10 |   random 1000000 |
|  fluxsort |  1000000 |   32 | 0.215098 | 0.216294 |       0.0 |      10 |   random 1000000 |
|           |          |      |          |          |           |         |                  |
|   pdqsort | 10000000 |   32 | 0.338767 | 0.342580 |         0 |      10 |  random 10000000 |
|  crumsort | 10000000 |   32 | 0.234268 | 0.234664 |         0 |      10 |  random 10000000 |
|  fluxsort | 10000000 |   32 | 0.264988 | 0.267283 |         0 |      10 |  random 10000000 |

Issues· 0 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

Cadaptivecin-placeinplace

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月18日
分类编程语言
定价开源

> 相关工具

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言