TimSort

A C++ implementation of TimSort, O(n log n) in worst case and stable sort algorithm, ported from Python's and OpenJDK's.

This is a bit slower than std::sort() on randomized sequences, and much faster on partially-sorted sequences.

SYNOPSIS

#include "timsort.hpp"

std::vector<string> a;

// initialize a

gfx::timsort(a.begin(), a.end(), std::less<string>());

TEST

Run make test for testing and make coverage for test coverage.

SEE ALSO

• http://svn.python.org/projects/python/trunk/Objects/listsort.txt
• http://en.wikipedia.org/wiki/Timsort

BENCHMARK

bench.cpp, invoked by make bench, is a simple benchmark. An example output is as follows (timing scale: sec.):

c++ -I. -Wall -Wextra -g  -DNDEBUG -O2 example/bench.cpp -o .bin/bench
c++ -v
Apple clang version 4.1 (tags/Apple/clang-421.11.66) (based on LLVM 3.1svn)
Target: x86_64-apple-darwin12.2.0
Thread model: posix
./.bin/bench
RANDOMIZED SEQUENCE
[int]
size	100000
std::sort        0.667322
std::stable_sort 0.895223
timsort          1.274456
[boost::rational]
size	100000
std::sort        4.152952
std::stable_sort 5.136133
timsort          5.781330
REVERSED SEQUENCE
[int]
size	100000
std::sort        0.087842
std::stable_sort 0.234953
timsort          0.017438
[boost::rational]
size	100000
std::sort        2.114911
std::stable_sort 2.247124
timsort          0.281315
SORTED SEQUENCE
[int]
size	100000
std::sort        0.086000
std::stable_sort 0.151913
timsort          0.010536
[boost::rational]
size	100000
std::sort        2.102378
std::stable_sort 2.408591
timsort          0.258270