En (ganska) enkel krets som (oftast) sorterar

Abstrakt:

Seminariet refererar en artikel från 1990 av Tom Leighton och C. Greg Plaxton.

Artikeln beskriver en parallell sorteringsmetod som bygger på den s.k. fjärilsturneringen. I denna får 2^k deltagare under k omgångar möta motståndare med samma mönster av förluster och segrar. Därför får spelare av liknande styrka tävla mot varandra, vilket bäddar för en snabb turnering.

På k omgångar blir fjärilsturneringen inte färdig. Artikeln ger exakta uppskattningar av hur stor andel av indatapermutationerna som ger utdata med måttliga fel i sorteringsordningen.

Genom att dela upp utdata från fjärilsturneringen i block och använda andra sorteringsmetoder på dessa skapar författarna en sorteringskrets som med mycket hög sannolikhet sorterar rätt.

Den informationsteoretiska undre gränsen är 2 lg n - o(lg n) omgångar. Leighton - Plaxtons algoritm är 10-potenser bättre än tidigare rekord och tar 7,44 lg n omgångar. Går det att göra bättre?