Sorting a set of items is a task that can be useful by itself or as a building block for more complex operations. That is why a lot of effort has been put into finding sorting algorithms that sort large sets as efficiently as possible. But the more sophisticated and fast the algorithms become asymptotically, the less efficient they are for small sets of items due to large constant factors. A relatively simple sorting algorithm that is often used as a base case sorter is insertion sort, because it has small code size and small constant factors influencing its execution time.
This thesis aims to determine if there is a faster way to sort these small sets of items to provide an efficient base case sorter. We looked at sorting networks, at how they can improve the speed of sorting few elements, and how to implement them in an efficient manner by using conditional moves. Since sorting networks
need to be implemented explicitly for each set size, providing networks for larger sizes becomes less efficient due to increased code sizes. To also enable the sorting of slightly larger base cases, we modified Super Scalar Sample Sort and created Register Sample Sort, to break down those larger sets into sizes that can in turn be sorted by sorting networks.
From our experiments we found that when sorting only small sets, the sorting networks outperform insertion sort by at least 25% for any array size between 2 and 16. When integrating sorting networks as a base case sorter into quicksort, we achieved far less performance improvements over using insertion sort, which is due to the networks having a larger code size and cluttering the L1 instruction cache. The same effect occurs when including Register Sample Sort as a base case sorter for IPS 4 o. But for computers that have a larger L1 instruction cache of 64 KiB or more, we obtained speed-ups of 6.4% when using sorting networks as a base case sorter in quicksort, and of 9.2% when integrating Register Sample Sort as a base case sorter into IPS 4 o, each in comparison to using  nsertion sort as the base case sorter.
In conclusion, the desired improvement in speed could only be achieved under special circumstances, but the results clearly show the potential of using conditional moves in the field of sorting algorithms.

Das Sortieren einer Menge von Elementen ist ein Prozess der für sich alleine nützlich sein kann oder als Baustein für komplexere Operationen dient. Deswegen wurde in den Entwurf von Sortieralgorithmen, die eine große Menge an Elementen effizient sortieren, bereits großer Aufwand investiert. Doch je ausgefeilter und schneller die Algorithmen asymptotisch sind, desto ineffizienter werden sie beim Sortieren kleinerer Mengen aufgrund hoher konstanter Faktoren. Ein relativ einfacher Sortieralgorithmus, der oft als Basisfall Sortierer genutzt wird, ist Insertion Sort, weil dessen Code kurz ist und er kleine konstante Faktoren hat.
Diese Bachelorarbeit hat das Ziel herauszufinden ob es einen schnelleren Algorithmus gibt um solche wenigen Elemente zu sortieren, damit dieser als effizienter Basisfall Sortierer genutzt werden kann. Wir haben uns dazu Sortiernetzwerke angeschaut, wie man durch sie das Sortieren kleiner Listen beschleunigen kann und wie man sie effizient implementiert: Durch das Ausnutzen von konditionellen move-Befehlen. Weil Sortiernetzwerke für jede Listengröße explizit implementiert werden müssen, nimmt die Effizienz des Sortierens mittels Sortiernetwerken wegen erhöhter Codegröße ab je größer die Listen sind, die sortiert werden sollen. Um auch das Sortieren etwas größerer Basisfälle zu ermöglichen haben wir Super Scalar Sample Sort modifiziert und Register Sample Sort entworfen, welcher eine größere Liste in mehrere kleine Listen zerteilt, die dann von den Sortiernetzwerke sortiert werden können.
In unseren Experimenten sind wir zu dem Ergebnis gekommen, dass, wenn nur kleine Mengen sortiert werden, die Sortiernetzwerke um mindestens 25% schneller sind als Insertion Sort, für alle Listen, die zwischen 2 und 16 Elementen enthalten. Beim Integrieren der Sortiernetzwerke als Basisfall Sortierer in Quicksort haben wir weit weniger Geschwindigkeitszuwachs gegenüber der Benutzung von Insertion Sort erhalten, was daran liegt, dass der Code der Netzwerke mehr Platz benötigt und den Code für Quicksort aus dem L1 Instruktionscache verdrängt. Derselbe Effekt tritt auch beim Benutzen von Register Sample Sort as Basisfall Sortierer für IPS4o auf. Allerdings konnten wir uns bei Rechnern, die über einen größeren L1 Instruktionscache von 64 KiB oder mehr verfügen, mit Sortiernetzwerken bei Quicksort um 6,4% und mit Register Sample Sort bei IPS 4 o um 9,2% gegenüber Insertion Sort als Basisfall Sortierer verbessern.
Zusammenfassend haben wir die angestrebte Verbesserung nur unter besonderen Bedingungen erreicht, aber die Ergebnisse weisen deutlich darauf hin, dass die konditionellen move-Befehle Potential im Anwendungsbereich von Sortieralgorithmen haben.