实现，而无需使用额外的阵列一个合并？

Question

最近我读了很多关于归并，我不知道是否有一种方法做一个合并，而不使用至少一个附加阵列。这可能吗？

Answer 1

根据维基百科这的确是可能的，但可能不会产生任何性能增益：

  

排序就地是可能的（例如，使用列表而不是数组），但非常复杂，并会提供在实践中很少的性能提升，即使在O算法运行（名词的日志< EM>名词的）时间。在这种情况下，如堆排序算法通常提供相当的速度，都远远不那么复杂。另外，与标准归并排序，就地归并排序不是一个稳定的排序。在链表的情况下，算法不使用更多的空间比已使用的列表表示，但（）记录（ķ）用于递归跟踪将O。有人会说，排序的链接列表不到位，因为即使你在给定的数据结构进行排序，数据结构本身具有O（名词的），额外的数据你操纵（例如，链接在列表中）。

Answer 2

显然，这是。 本文介绍就地归并排序：

  

两个就地经典归并算法的变体进行了详细的分析。至多第一，简单的变型中进行N日志2 N + O（N）的比较和3N日志2 N + O（N）移动到N个元素进行排序。第二，更先进的变体需要最多N日志2 N + O（N）的比较和“N日志2场N移动时，对于任何固定的”？ 0和任何N + N（“）。从理论上讲，第二个是优于堆排序的高级版本。在实践中，由于指数操作的开销，我们增长最快就地归并的行为仍有约50％，比自下而上的堆排序慢然而，我们的实施方式中与基于就地合并归并算法是实用的。

Jyrki Katajainen，托米帕萨宁，的Jukka Teuhola， “实用就地归并”（1996）。

Answer 3

下面是Java实现

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {

    for (int i = 1; i <seed.length; i=i+i)
    {
        for (int j = 0; j < seed.length - i; j = j + i+i)
        {
            inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
        }
    }       
}
public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

下面是单元测试

private Integer[] seed;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
    ArrayUtils.<Integer>iterativeMergeSort(seed);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(seed, equalTo(result));  
}

Answer 4

没有，你总是需要一个额外的数据结构合并排序的元素。如果不是你只被覆盖的东西，你已经排序。