For Perl kind of performance Tree:RB is ultra fast but look at Ruby's standard red and black tree, it is several orders of magnitude faster. The Ruby gem rbtree is just C code bind for dict.c, you can download it here https://rubygems.org/gems/rbtree Inside the gem file there is dict.c and dict.h, as well as ruby.c which is the wrap.

If Tree::RB takes 33 seconds and the Ruby gem rbtree takes 2 seconds, then it's an exaggeration to say it's 'several orders of magnitude faster'; based on those numbers, it's one order of magnitude faster.

And if the Ruby solution is just C code that you can download, how about just using Inline::C to wrap that code and use it as is.

However, I have to ask my favourite question, which is "What problem are you trying to solve?" Why are you looking for something that sorts stuff? Is there any way you could put the data you have into a database, and have it deal with whatever operation you're trying to do?

The beauty of using a database is that lots and lots of hard work has already been done on handling millions of rows efficiently; handling filtering, sorting and selection of those rows is what a database does. You can also have multiple tasks that add data, grab chunks of it, and delete stuff that's been processed.