Верно ли, что чем сильнее «разрознен» массив чисел, тем больше времени займет его сортировка (допустим, пузырьком)?
Для сортировки пузырькомимеет значение не средневзвешенное, а только максимальное отклонение позиции элемента от верной.То есть, другими словами, если вы в отсортированном массиве только поменяете местами крайние элементы, то его сортировка пузырьком займет максимально возможное время.определенно да.
Для приведенного подхода(отдельно сортировать части потом слить) применяют сортировку слиянием merge-sort.
1. В общем случае, нет.
2. Возможно, да, возможно, нет. Сильно зависит от используемого алгоритма и элементов массивов.