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

Question

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

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

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

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

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

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

Answer 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);
}