Sortieren: wann geht es schneller?

(sequentiell, parallel und extern) sind scharfe untere Schranken
bekannt. Andererseits gibt es algorithmen, das bekannteste Beispiel
ist Bucketsort, die unter diese Schranken hinaus kommen. Das ist
m\"oglich weil man entweder ein etwas einfacheres Problem betrachtet,
oder weil man etwas tut, das nicht vom Unterschrankenbeweis abgedeckt
wird.

In diesem Vortrag werde ich versuchen eine Antwort zu geben auf
der Frage in welchen F\"allen die unteren Schranken gesprengt werden
k\"onnen. Die folgenden Probleme werden dabei betrachtet: Sortieren
auf rekonfigurierbaren Prozessornetzen, Sortieren uniformer
Verteilungen, Sortieren ohne Umordnen, padded Sorting und
word-level Parallelismus.