WikiSort is an implementation of "block merge sort", which is a stable merge sort based on the work described in "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner [PDF].
Block merge sort, or "block sort" for short, is generally as fast as a standard merge sort while using O(1) memory, and is even faster when the input is partially ordered. Block sort can also be modified to use any additional memory optionally provided to it, which can further improve its speed.
C, C++, and Java versions are currently available, and you have permission from me and the authors of the paper (Dr. Kim and Dr. Kutzner) to do whatever you want with this code.
If you want to learn how it works, check out the documentation:
• Chapter 1: Tools
• Chapter 2: Merging
• Chapter 3: In-Place
• Chapter 4: Faster!
Or you can check out the work-in-progress version of the Wikipedia page that is currently waiting for review. Technically block sort is still a merge sort despite requiring the use of some other sorting algorithm like insertion sort to function properly, but it was too detailed to justify putting in the existing in-place merge sort page.
WikiSort vs. std::stable_sort()
(clang++ version 3.2, sorting 0 to 1.5 million items)
Using a 512-item fixed-size cache for O(1) memory:
Test Fast comparisons Slow comparisons 150,000,000 items 0-32 items
Random 3% faster 95% as fast 21% faster 42% faster
RandomFew 1% faster 19% faster 28% faster 40% faster
MostlyDescending 98% as fast 16% faster 96% as fast 48% faster
MostlyAscending 150% faster 116% faster 313% faster 46% faster
Ascending 1164% faster 487% faster 77% faster 233% faster
Descending 22% faster 128% faster 23% faster 172% faster
Equal 1158% faster 426% faster 831% faster 241% faster
Jittered 470% faster 287% faster 565% faster 66% faster
MostlyEqual 17% faster 60% faster 19% faster 39% faster
Append 165% faster 86% faster 1% faster 107% faster
Using a dynamically allocated half-size cache:
Test Fast comparisons Slow comparisons
Random 11% faster 2% faster
RandomFew 15% faster 6% faster
MostlyDescending 38% faster 35% faster
MostlyAscending 96% faster 80% faster
Ascending 812% faster 450% faster
Descending 75% faster 176% faster
Equal 822% faster 462% faster
Jittered 321% faster 244% faster
MostlyEqual 18% faster 5% faster
Append 155% faster 98% faster