Как перевести мою логику решения в доказательство?
Найти k - позицию максимального элемент. Если k < n, то сделать 2 шага: разворот 1...k  и разворот 1...n. Теперь максимум точно в конце, и задача свелась к сортировке первых n-1 чисел.
Индукцией вроде так:
1. База: ряд из 2-х элементов - либо уже отсортирован, либо сортируется переворачиванием всего ряда.
2. Пусть мы знаем как отсортировать ряд из k элементов, рассмотрим ряд a_1 ... a_k a_k+1, где первые k элементов отсортированы. Далее три случая:

a_k+1 больше всех a_1 ... a_k - ряд уже отсортирован
a_k+1 меньше всех a_1 ... a_k - переворачиваем a_1 ... a_k, затем переворачиваем обратно весь ряд (a_k ... a_1 a_k+1)
a_k+1 должен идти по порядку между некоторыми a_m и a_m+1:

переворачиваем весь ряд a_1 ... a_k+1 
переворачиваем ряд a_k+1 ... a_m+1 (получится: a_m+1 ... a_k a_k+1 a_m a_m-1 ... a_1)
переворачиваем ряд a_m+1 ... a_k (получится: a_k ... a_m+1 a_k+1 a_m a_m-1 ... a_1) - новый элемент в нужной позиции
переворачиваем снова весь ряд

