Задача Александра Ивановича Корейко

Получилось перемножать трехзначные числа в уме после тренировок. Двухзначные получается всегда. В столбик.
Помогает округление. Например 83*27=83*3*10-83*3
В данном случае 423*836=425*836-2*836=400*836+836/4*100-2*836=334400+20900-2*863=355300-1672=353628 (честно посчитал в уме, один раз сбился и начал заново)

Внешняя сортировка с O(1) дополнительной памяти

O(S^2): Мы делаем S проходов, и для каждого K от 1 до S делаем S-1 слияний с первым блоком и столько же с последним. Получается S(S-1) слияний.

Внешняя сортировка с O(1) дополнительной памяти

Не совсем. In-place merge sort это вариант сортировки слиянием, который не использует внешний буфер. При этом весь массив находится в памяти.
Для внешней сортировки (когда данные не помещаются в памяти) нельзя использовать те же алгоритмы, это будет слишком медленно. Этот алгоритм — внешняя сортировка, точнее, её вариант, не требующий буфера на диске. Он может пригодится, например, если вам нужно отсортировать 980Гб данных на терабайтном диске (хотя это и займет кучу времени, судя по всему).