Отсортировать массив с помощью медленной сортировки

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы отсортировать данный массив в порядке возрастания, используя медленную сортировку.

Примеры:

Input: arr[] = {6, 8, 9, 4, 12, 1}
Output: 1 4 6 8 9 12

Input: arr[] = {5, 4, 3, 2, 1}
Output: 1 2 3 4 5

Подход: как и сортировка слиянием , медленная сортировка представляет собой алгоритм «разделяй и властвуй» . Он делит входной массив на две половины, называет себя двумя половинами, а затем сравнивает максимальный элемент двух половин. Он сохраняет максимальный элемент подмассива в верхней позиции подмассива, а затем рекурсивно вызывает подмассив без максимального элемента. Выполните следующие шаги, чтобы решить проблему:

Медленная сортировка (обр[], л, г):

• Если r >= l , выполните следующие шаги:
  • Найдите среднее значение массива как m = (l + r)/2 .
  • Рекурсивно вызовите функцию SlowSort, чтобы найти максимум элементов первой половины: SlowSort(arr, l, m)
  • Рекурсивно вызовите функцию SlowSort, чтобы найти максимум элементов второй половины: SlowSort(arr, m + 1, r)
  • Сохраните наибольший из двух максимумов, возвращаемых вышеприведенными вызовами функций, в конце как arr[r] = max(arr[m], arr[r])
  • Рекурсивно вызвать функцию SlowSort без максимума, полученного на предыдущем шаге: SlowSort(arr, l, r-1)

На следующем рисунке показан полный процесс медленной сортировки . Например, массив {9, 6, 8, 4, 1, 3, 7, 2} . Из рисунка видно, что массив рекурсивно делится на две половины, пока размер не станет равным 1. Как только размер станет равным 1, начнется процесс сравнения.

Ниже приведена реализация вышеуказанного подхода:

Лучшая временная сложность случая: , где е > 0
Средняя сложность рассмотрения дела:
Вспомогательное пространство: O(1)