Рекурсивная сортировка слиянием C ++

Question

Я хочу написать рекурсивную программу сортировки слиянием на C ++. Проблема в том, что я не знаю, как заставить идею базового случая работать рекурсивно. Кто-нибудь может сказать, пожалуйста, какой будет базовый вариант для функций Merg Function(), Split Function() и MergSort(). Я был бы благодарен вам.

void Merg(int A[], int s1, int e1, int s2, int e2)
{
   int B[8];
   int i=0;

   while (A[s1] < A[s2])
      B[i] = B[s1];
      i++;
      s1++;

      if (s1 == e1)
      {
         B[i] = A[s2];
         i++;
         s2++;
      }

   while (A[s2] < A[s1])
      B[i] = B[s2];
      i++;
      s2++;

      if (s2 == e2)
      {
         B[i] = A[s1];
         i++;
         s1++;
      }
}

void Split(int A[], int s, int e)
{
   int mid = (s+e)/2;

   if (s < e && mid != 0)
   {   
      Split(A, s, mid);
      Split(A, mid+1, e);   
   }
   Merg(A, s, mid, mid+1, e);
}

int main()
{
   int A[8] = {10,4,8,12,11,2,7,5};

   Split(A, 0, 7);

   return 0;
}

Answer 1

Базовым регистром является массив, который гарантированно будет отсортирован, поэтому либо пустой массив, либо массив длиной 1.

Ваша функция слияния неверна, но, по крайней мере, содержит большинство правильных идей,Все, что вам нужно, - это дальнейшая петля обёртывания и несколько условий, чтобы предотвратить слияние после окончания массивов.Функция разделения полностью отключена, разделение не является рекурсивным, дальнейшие разбиения происходят внутри рекурсивных вызовов mergeSort.

1. , если длина (A) <2, возврат // уже отсортирован </li>
2. разделить A на нижнюю половину L и верхнюю половину H
3. сортировка слиянием L
4. сортировка слиянием H
5. объединение отсортированных L и H
6. done