Skip to content

Highly-optimized sorting implemention in C++, including insertsort, shellsort, heapsort, quicksort, mergesort, timsort

License

Notifications You must be signed in to change notification settings

Baobaobear/sort

Repository files navigation

Sort

Build StatusAppveyor status LanguageStandardLicense

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 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.

About

Highly-optimized sorting implemention in C++, including insertsort, shellsort, heapsort, quicksort, mergesort, timsort

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published