Что на месте сортировать, когда два массива в порядке?

Я работаю над этим вопросом . Мой прототип функции - 

static void Sort(byte[] arr, int leftPos, int rightPos)

Во 2-й части функции я знаю, что leftPos к leftPos + (rightPos-leftPos)/2 и (rightPos-leftPos)/2 к rightPos отсортированы по порядку.

Я пытался думать о том, как я мог бы сделать сортировку на месте, зная, что две части в порядке. Я ничего не мог придумать. Я посмотрел на функцию merge в merge sort , но она использует выходной массив, а не на месте.

Как мне отсортировать его на месте зная, что оба ломтика в порядке?

Примечание: Я думал, что могу передать дополнительный массив, который имеет ту же длину, что и основной массив, чтобы использовать его в качестве временной памяти, но способ, который я придумал, потребует от меня сделать массив.Копирование после каждого слияния.

1 2
sorting algorithm in-place

1 ответ:

Слияние на месте возможно, но это сложно и не дает большого прироста производительности. Ниже приведен пример кода из здесь . from является ли ваш leftPos, to это ваш rightPos, pivot является вашим (rightPos-leftPos)/2, а длины-это длины каждой половины.

void merge(int from, int pivot, int to, int len1, int len2) {
  if (len1 == 0 || len2==0) return;
  if (len1+len2 == 2) {
   if (compare(pivot, from) < 0)
    exchange(pivot, from);
   return;
  }
  int first_cut, second_cut;
  int len11, len22;
  if (len1 > len2) {
   len11=len1/2;
   first_cut = from + len11;
   second_cut = lower(pivot, to, first_cut);
   len22 = second_cut - pivot;
  } else {
   len22 = len2/2;
   second_cut = pivot + len22;
   first_cut = upper(from, pivot, second_cut);
   len11=first_cut - from;
  }
  rotate(first_cut, pivot, second_cut);
  int new_mid=first_cut+len22;
  merge(from, first_cut, new_mid, len11, len22);
  merge(new_mid, second_cut, to, len1 - len11, len2 - len22);
}
1