# 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.