63
правки
Изменения
Нет описания правки
|$O(n \log \log n)$
|Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.
|- align = "center"
|[[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием <br>(Multithreaded merge sort)]]
|$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$
|$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$
|$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$
|$O(n)$
|Да
|$O(n \log n)$
|Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток.
|- align = "center"
|[[PSRS-сортировка|PSRS-сортировка <br>(PSRS-sorting)]]
|$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$
|$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$
|$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$
|$O(N_{ind}^2)$
|Нет
|$O(n \log n)$
|Разделим массив на $N_{ind}$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы.
|}
== Источники информации==
