Чтобы найти наименьший размер перемешанного отрезка, можно отсортировать копию исходного массива и найти первый и последний элементы, стоящие не на своих местах. Они и будут концами искомого отрезка. Максимальный по размеру отрезок — это всегда весь исходный массив.