Wszyscy wiemy, że minimalną złożonością algorytmu sortowania opartego na porównaniu są porównania . Próbuję wykonać sortowanie w ciemno , tzn. Biorąc pod uwagę liczbę wyjdź z obwodu (z bramkami logicznymi, arytmetycznymi i „porównawczymi”), który sortuje listę elementów.
Wstępne obliczanie wszystkich porównań select 2}, a następnie wykonywanie arytmetyki na wynikowych bitach, daje mi algorytm , jednak myślę, że dzięki zwariowanej "arytmetyki wskaźnika" myślę, że mogę uzyskać wersja.
Czy istnieje znana dolna granica dla obwodów sortujących na podstawie porównania wzdłuż podobnych linii do dla algorytmu sortowania na podstawie porównania? Czy może być nawet możliwe sortowanie w ciemno w czasie ?
n^2
jest dolna granica, czy też nie można go sprowadzić do zwykłego - n log n
po prostu sprawdzam, czy są jakieś sytuacje, w których wyższa granica, taka jak n^2
już jest znana.