Sort

Overview

This is a highly-optimized sorting library, compatible with C++03

Algorithm table

Algorithm	Stable	Best	Average	Worst	Mem	Header	Name
Insertion sort	yes	n	n²	n²	1	sortlib.hpp	insert_sort
Heapsort	no	n	n㏒n	n㏒n	1	sortlib.hpp	heap_sort
Shellsort	no	n	n5/4 ?	n4/3	1	sortlib.hpp	shell_sort
Quicksort	no	n	n㏒n	n㏒n	㏒n	sortlib.hpp	quick_sort
Quicksort indirect	yes	n	n㏒n	n㏒n	n	sortlib.hpp	indirect_qsort
Mergesort	yes	n	n㏒n	n㏒n	n	sortlib.hpp	merge_sort
Mergesort buffer	yes	n	n㏒²n	n㏒²n	√n	sortlib.hpp	merge_sort_buffer
Mergesort in-place	yes	n	n㏒²n	n㏒²n	㏒n	sortlib.hpp	merge_sort_in_place
Timsort	yes	n	n㏒n	n㏒n	n	sortlib.hpp	tim_sort
Timsort buffer	yes	n	n㏒n	n㏒n	√n	sortlib.hpp	tim_sort_buffer
Radixsort in-place	no	n	n	n	1	sortlib.hpp	radix_sort_in_place
Grailsort	yes	n	n㏒n	n㏒n	√n	grailsort.hpp	grail_sort
Grailsort buffer	yes	n	n㏒n	n㏒n	1	grailsort.hpp	grail_sort_buffer
Grailsort in-place	yes	n	n㏒n	n㏒n	1	grailsort.hpp	grail_sort_in_place
Wikisort	yes	n	n㏒n	n㏒n	1	wikisort.hpp	wiki_sort

Timsort: Tim Peter's original implementation

Usage

Here is the demo, or you can try demo.cpp

#include "sortlib.hpp"
#include <cstdlib>

int main(void)
{
    std::vector<int> arr(100);

    for (size_t i = 0; i < arr.size(); i++)
    {
        arr[i] = rand();
    }

    baobao::sort::tim_sort(arr.begin(), arr.end());
    return 0;
}

Call it like STL as well

Note

merge_sort_s, merge_sort_buffer_s, tim_sort_s is the safe copy version if you overload operator = and do something different

Performance

Run the code sorttest.cpp, it will output the result

Build with g++ -std=c++03 -O3 sorttest.cpp on Centos 7 x64, gcc version is 8.3.1

Functions name with bao_ perfix are in sortlib.hpp header
Functions name with grail_ perfix are in grailsort.hpp header
std_qsort is the qsort function in stdlib.h header

Sorting 2,000,000 TestClass

TestClass 8	1	2	3	4	5	6	7	8	9	10	11	Avg
bao_qsort	10	24	32	163	160	59	61	80	98	161	123	88
bao_radix_in	40	63	76	121	145	75	83	66	74	135	99	88
std::sort	121	61	65	173	184	141	129	84	106	166	143	124
bao_tim	6	9	19	272	244	225	158	11	94	245	155	130
bao_merge	6	18	184	255	247	212	177	75	74	253	128	148
bao_tim_buf	6	9	17	372	358	243	193	11	88	316	125	158
bao_mer_buf	5	21	135	326	371	256	198	66	96	335	148	177
bao_shell	9	13	132	425	431	226	172	100	112	412	155	198
wiki_sort	17	67	237	399	418	350	296	155	204	363	170	243
bao_mer_in	6	17	137	573	603	308	248	64	103	524	186	251
std::stable	305	332	330	338	338	342	309	286	304	355	155	308
std_qsort	206	205	295	546	526	413	344	248	270	464	306	347
grail_sort	92	301	347	503	499	492	325	327	300	451	291	357
bao_heap	32	221	212	845	792	319	303	197	203	833	217	379
bao_indir	102	74	59	754	838	618	640	113	161	745	171	388
std::heap	219	253	294	852	840	353	326	197	245	899	235	428

Sorting 4,500,000 int

int	1	2	3	4	5	6	7	8	9	10	11	Avg
bao_radix_in	41	110	105	164	228	79	73	117	118	163	165	123
bao_qsort	4	11	24	303	292	71	41	76	110	290	217	130
bao_tim	2	2	9	362	353	156	80	6	114	339	222	149
bao_tim_buf	2	3	8	399	387	155	84	9	116	376	218	159
std::sort	62	65	66	304	315	121	109	75	137	305	230	162
bao_merge	4	20	84	378	352	183	105	63	115	345	246	172
bao_mer_buf	6	15	65	406	381	188	112	70	117	376	254	180
bao_shell	4	5	71	483	451	178	61	40	95	427	233	186
std::stable	105	99	99	374	366	175	95	104	164	361	254	199
wiki_sort	16	41	89	466	449	264	146	89	162	440	260	220
grail_sort	61	116	141	445	475	438	195	125	177	435	445	277
std_qsort	143	154	181	536	555	345	235	171	261	542	419	322
bao_mer_in	3	15	129	944	942	329	283	67	150	912	367	376
bao_heap	9	242	272	883	956	297	308	236	260	892	328	425
std::heap	235	255	272	969	969	310	311	249	309	950	383	473
bao_indir	123	86	109	1561	1556	1219	1261	219	290	1398	357	743

Benchmark of random shuffle data

The x-axis is log2(length)

The y-axis is time / length * 1000000

Sorting TestClass

Sorting int

License

This project is licensed under the MIT License.