当两个数组有序时，如何进行就地排序？

我正在研究这个问题 https://stackoverflow.com/questions/4673854/sort-with-threads/4674052。我的函数原型是

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

在函数的第二部分中，我知道 leftPos 到 leftPos + (rightPos-leftPos)/2 和 (rightPos-leftPos)/2 到 rightPos 按顺序排序。

我尝试思考如何在知道这两个部分按顺序进行的情况下进行就地排序。我想不出任何一个。我查看了合并功能归并排序 http://en.wikipedia.org/wiki/Merge_sort但它使用输出数组而不是就地数组。

知道两个切片都按顺序排列时，如何对其进行排序？

注意：我想我可以传入一个与主数组长度相同的额外数组用作临时内存，但我想到的方式需要我在每次合并后执行 Array.Copy 。

就地合并是可能的，但它很复杂并且不会带来太多性能提升。下面是一些示例代码here http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html. 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);
}