New sorting algorithm (I hope so, anyway)

ta0kira · 02-09-2008, 07:57 PM

I came up with an optimization to the Merge Sort algorithm about 2 months ago for my C++ template list library. While I know I sat down and figured it out on my own, I was wondering if it's a duplication of something similar out there. The reason I ask is that it seems entirely too simple of a concept for no one to have come up with it earlier. Of course, I don't imagine many other people sit down to write sorting algorithms.

If you have an interest in data processing algorithms please take a few minutes to check out my work. It's literally a 7-minute read with pictures and everything. It's open-source for those who want to use and abuse it.

The main point-of-interest is its lack of recursion and allocation required by most Merge Sort implementations. You need only create iterators, place markers, and at most 1 temporary element. The page has a link to download a package containing a standalone header.

Please let me know what you think. I don't mind if I actually did waste my time reinventing something that didn't need to be. I just like how the pictures came out

Circular Insertion Merge Sort

ta0kira

billymayday · 02-09-2008, 08:11 PM

Interesting. Only had a quick read, and it's a long time since I did my compsci degree, so don't recall sorting algorithms that well.

I do think your central tenet that people don't sit around and think about sorting algorithms is probably wrong. Back in the "old days" - only tape (or worse still cards) - sorting was a big issue because inefficiency slowed things enormously. These days I'm sure the googles of the world spend plent of time on the issue. As databases get bigger, sorting (and related fields like indexing) remain critical.

Anyway, good luck

binutils · 02-09-2008, 08:20 PM

Hi,
any benchmark result?

ta0kira · 02-09-2008, 08:48 PM

Nothing official, but (as far as I remember) it kicks the ass off of std::stable_sort and std::sort at -O3 and -O0 but loses slightly at -O1 and -O2. I think that's just a matter of algorithm style and the optimzation rules used by g++. In any case, it's competitive enough with built-ins to be a direct replacement, plus 3 additional features (reverse order, reverse of equal elements, sorting across the end of the array.)

The main reason I use it is to be able to sort across the end of a list for my template library like this, which can be done at the same speed as conventional sorting:

Code:

[ 5 6 3 2 6 7 8 9 1 2 3 4 5 6 7 ] (before)
  end==>|             |start==>
[ 5 6 6 7 6 7 8 9 1 2 2 3 3 4 5 ] (after)

ta0kira

ta0kira · 02-10-2008, 02:40 PM

(edit: it seems I was grossly mistaken; it has a huge problem I didn't notice before...)
ta0kira