Введение в программирование 3. Сортировки. MergeSort, недетерминированный QuickSort

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 17 сентября 2021 года Лектор: Степанов Илья Даниилович Оператор: Мария Шкатова Монтаж: Жильцов Игорь 0:00 - Сортировка. Постановка задачи 04:50 - Теорема: асимптотика работы сортировки, основанной на сравнениях, в худшем случае 07:00 - Сравнения 08:30 - Лемма. log(n!) = Θ(n log n) 17:15 - Доказательство теоремы 33:00 - MergeSort (сортировка слиянием) 40:35 - Функция Merge 45:13 - Корректность сортировки слиянием 48:50 - Оценка памяти 50:03 - Количество инверсий 01:00:00 - Нерекурсивная реализация MergeSort 01:10:30 - Недетрминированный QuickSort (быстрая сортировка)