Course Project: Parallel Sorting of an Intransitive Ordered Set
Project Proposal: Sorting of Transitive Total Ordered Sets is one of the most researched topics in Computer Science. A generalization of this is sorting an Intransitive Total Ordered Set which is, therefore, more complex. While for a Transitive Total Ordered Set (e. g. a subset of the real numbers) holds a >= b and b >= c implies a >= c, this does not have to be true for a Intransitive Total Ordered Set. Only a > b xor b > a is claimed. Nevertheless, it can be proven that there is always an ordering that satisfies a1 >= a2 >= a3 >= ... >= an. A good example for such a set is a tournament. Each competitor either wins or loses against every other competitor. But even if it is known that Player A defeats Player B who defeats Player C in turn, nothing can be said about the result of the match Player A versus Player C.
One of the papers listed below proposes an algorithm for sorting such a set on a EREW PRAM in parallel. I implemented this algorithm for a shared memory system using pthread and to compare it to the best known sequential algorithm, as well as to ordinary sorting algorithms.
Startup Papers: Jie Wu: On Sorting an Intransitive Total Ordered Set
Using Semi-Heap
Jie Wu, Stephen Olariu: On Cost-Optimal Merge of two Intransitive Sorted
Sequences
Slide Presentation (PowerPoint File) incl.
Question Sheet and Demo Program (for Windows, .NET Runtime required)
Final Paper (PDF) and
C-Source-Code of the implementation.