Adaptive Sort

A sorting algorithm is born: ASort

A couple of months ago I needed a sort method in a project I was working on, and instead of using the available .NET sort I decided to write my own (just for the fun of it). I started with implementing a Quicksort and Merge sort, but I didn't like either of them. Quicksort is a beautiful algorithm, but isn't very efficient once you have time consuming comparison methods, and merge sort requires Θ(n) in memory. I even tried some other well known sorting algorithms like Heap sort but that one was awful (or maybe I just implemented it badly).

Another problem with the common sorting algorithms is that they usually don't adapt to the data. Neither quicksort nor merge sort gives optimal results in partially ordered data (quicksort can even give Θ(n2) performance), and adding a preprocessing pass only gets you so far.

Naturally, at this point I had abandoned the original project and lost myself into the jungle of sorting algorithm. Finally I figured out a way to combine adaptive sorting and efficient sorting of random data, and the ASort algorithm was born (A stands for Adaptive).

On this site you can read about Quicksort and Merge sort, and even see the code I used to test them, and you can also read a little more about ASort and a detailed report of how it compares to Quicksort and Merge sort. However, the ASort algorithm became very efficient so I will not describe the algorithm in details (maybe I can make some money out of it).

About me
Humanus per a computer

I'm a software developer and system architect with over 20 years of experience in advanced software development.

I have studied computer science and math and written chess programs and other AI software.

Also, please check out my commercial project Xtreme Route. Routing was never easier nor faster!

To get in contact with me, use the guestbook or send me an email.