Designing Efficient Algorithms for Parallel Computers

Michael Jay Quinn

Mentioned 1

Mathematics of Computing -- Parallelism.

More on

Mentioned in questions and answers.

Our algorithm professor gave us a assignment that requires us to choose a rare sorting algorithm (e.g. Introsort, Gnomesort, etc.) and do some research about it. Wikipedia sure has a plenty of information about this, but it is still not enough for me to do the research in depth. So I would like to find a book that include discussions of those rare sorting algorithms, since most of the textbooks (like CLRS, the one I am using) only discuss about some basic sorting algorithms (e.g. Bubble Sort, Merge Sort, Insertion Sort.). Is there a book or website that contains a good amount of those information? Thanks!

One of a sorting which may be you say Rare Sorting, is timsorting, It works great in arrays which are have sorted parts, best case is O(n), and worst and average case is O(n log n).

Another fast way of sorting is bitonic sorting, which is base of nearly all parallel sorting algorithms. you can find thousands of papers about in the web, also some books like Parallel algorithm of Quinn you can find extended discussion on it, and related variations of this algorithm.

Also Art of computer programming volume 3 has good discussion on sorting strategies.

Realated tags