Optimizing Sort and Search algorithms

[bozo]

ok, so most comp programming students will have at least encountered basic bubble sort and binary search algorithms.

i was curious if there were any efforts to optimize any of these search and sort algorithms..say for example using SSE2 if that were possible.

i've not researched the possibility of using sse2 (yet) to speed up sorting or searching but am curious to find out..anyone here ever try?

[dedndave]

i think it is the favorite pastime of some of these guys - lol
use the forum search tool - advanced search
you can narrow it down by specifying the author
try hutch--, drizz, jj2007, lingo
and a few others - all good programmers that like to do that stuff

EDIT - Hutch used to have a link for some Boyer-Moore stuff - i don't remember if it was SSE2 or not
anyways - the link is gone, now - maybe he can point you in the right direction

EDIT - this may be it...
http://www.movsd.com/bm.htm

[hutch--]

A BM algo is probably the wrong algo type to try this on as there is little chance of any parallelism in its design. If memory is not a problem sorting can probably be done with some parallelism, particularly if you know what a pidgeonhole sort works like.

Strangely enough a bubble sort is not entirely useless, they perform well on nearly sorted data but from memory an insertion sort will still beat it in that context.

[Neo]

Comb sort is one of the few that actually vectorizes easily and is nlogn.  Unfortunately, some jerk has a patent application filed on vectorized comb sort: http://www.google.com/patents/about?id=dCOiAAAAEBAJ  :(  Hopefully the patent reviewers require them to tie it to the non-x86-based hardware they're describing it for, 'cause it's utterly ridiculous.

[hutch--]

Just do a double ended comb sort (cocktail shaker bubble sort applied to a comb sort). They are OK in that they are near impossible to lock up with deliberately structured data but quick sorts generally havve the legs on them.

[Neo]

Good thinking!  I don't think that'd qualify as "invoking a comb sort algorithm", so then their patent's claims wouldn't cover it.  :bg