1. Quicksort revised
1.1 За O(log n) доп памяти
1.2 Доказательство QSort через матожидание числа сравнений

2. Nth-Element
2.1 Как одноветочный QSort
2.2 Анализ, аналогия с обычным Qsort, без доведения до конца
2.3 Простой Анализ
2.4 Рассказ об nth_element в C++
2.5 Детерминизируем nth-element, median of medians

3. Сортировки целых чисел
3.1 Ещё раз о countsort, теперь хитрее
3.2 Stability: +
3.3 Сортируем пары <ai, bi>, сначала по ai, а потом и лексикографически
3.4 сортируем строки
3.5 Сортируем чиселки за n log_n (m)
3.6 BucketSort, BB, BI
3.7 max-min <= n -> BB, BI за O(n)
3.8 BB за O(n log (max - min))
3.9 BI за O(n) если все числа случайно выбраны как uniform i.i.d.

4. VEB