Sortierverfahren
Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Menge von Werten zu sortieren. Voraussetzung ist, dass auf den Werten eine Ordnung existiert, etwa die alphabetische Ordnung von Zeichenketten. Die Folge wird liegt üblicherweise in Form eines Arrays vor.
Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten. Die Komplexität eines Algorithmus wird üblicherweise in der Landau-Notation dargestellt. Einige Sortierverfahren benötigen außerdem neben dem zur Speicherung des Arrays nötigen noch weiteren Speicherplatz. Komplexität und Speicherbedarf hängen bei einigen Sortierverfahren vom vorliegenden Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall).
Man unterscheidet zudem zwischen stabilen und unstabilen Sortierverfahren sowie zwischen solchen, die in-place arbeiten, d.h. die ohne zusätzlichen Speicherplatz funktionieren, und solchen, die dies nicht tun.
| Sortierverfahren | Komplexität | stabil | zusätzlicher Speicherbedarf |
| BinaryTreeSort | O(n·log(n)) | ja | O(n) |
| BogoSort | O((n/2)!) | nein | O(n) |
| BubbleSort | O(n2) | ja | - |
| BucketSort | O(n) | ja | O(n) |
| CocktailSort (ShakerSort) | O(n2) | ja | - |
| CombSort | O(n·log(n)) | nein | - |
| CountingSort | O(n+k) | ja | O(n+k) |
| HeapSort | O(n·log(n)) | nein | - |
| InsertionSort | O(n2) | ja | - |
| MergeSort | O(n·log(n)) | ja | - |
| PigeonholeSort | O(n+k) | ja | O(k) |
| QuickSort | O(n·log(n)), im Worst Case O(n2) | nein | - |
| RadixSort | O(n·log(k)) | nein | O(n) |
| SelectionSort | O(n2) | ja | - |
| ShellSort | O(n·1,25) | ja | - |
| SmoothSort | O(n·log(n)) | nein | - |