sorteernetwerk

Sorteernetwerk is een vast ontwerp van hardware- of softwarecomponenten dat wordt gebruikt om een reeks van n invoerwaarden te sorteren. Het bestaat uit meerdere parallelle kanalen, oftewel draden, en een verzameling vergelijkers. Een vergelijker vergelijkt twee naast elkaar liggende waarden en stuurt de kleinere waarde naar één uitgang en de grotere waarde naar de andere uitgang. De lay-out is deterministisch en afhankelijk niet van de invoerwaarden, waardoor het netwerk data-oblivious (gegevensonafhankelijk) sorteert.

In het netwerk worden de vergelijkers gegroepeerd in fasen of lagen, waarin tegelijk meerdere vergelijkingen kunnen plaatsvinden. De volgorde van de vergelijkers is vast; bij elke invoer passeert de data langs de verschillende lagen en eindigt uiteindelijk in een geordende uitvoer. De belangrijkste eigenschappen zijn de grootte (aantal vergelijkers) en de diepte (aantal fasen). Deze deterministische structuur maakt sorteernetwerken geschikt voor hardware-implementaties en voor parallelle sortering op gespecialiseerde apparaten.

Voorbeelden van bekende sorteernetwerken zijn Batcher's bitonic sorter en odd-even mergesort. Deze netwerken sorteren n elementen met een vaste structuur en hebben een begrensde diepte en grootte, wat resulteert in voorspelbare prestaties.

Voordelen zijn voorspelbaar gedrag en eenvoudige implementatie in hardware; nadelen zijn gebrek aan adaptiviteit en mogelijk hogere hardware- of ruimtekosten vergeleken met adaptieve of softwarematige sorteeralgoritmen.