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

Question

В последнее время я много читал о сортировке слиянием, и мне интересно, есть ли способ выполнить сортировку слиянием без использования хотя бы одного дополнительного массива. Возможно ли это?

Answer 1

Видимо, так и есть. В этой статье описывается сортировка слиянием на месте:

Детально проанализированы два варианта классического алгоритма слияния на месте. Первый простой вариант выполняет не более N log 2 N + O (N) сравнений, а 3N log 2 N + O (N) перемещается для сортировки N элементов. Второй, более продвинутый вариант требует не более N log 2 N + O (N) сравнений и «N log 2 N перемещений для любого фиксированного»? 0 а какой Н? N ("). Теоретически, второй вариант превосходит расширенные версии heapsort. На практике из-за издержек, связанных с манипулированием индексами, наша самая быстрая на месте сортировка ведет себя примерно на 50% медленнее, чем восходящий heapsort Однако наши реализации практичны по сравнению с алгоритмами сортировки слиянием, основанными на слиянии на месте.

Юрки Катаяйнен, Томи Пасанен, Юкка Теухола, "Практическое объединение на месте" (1996).

Answer 2

Согласно Википедии это действительно возможно, но может не дать никакого прироста производительности:

Сортировка на месте возможна (например, с использованием списков, а не массивов), но она очень сложна и на практике даст небольшой выигрыш в производительности, даже если алгоритм работает за O ( n log п ) время. В этих случаях алгоритмы, такие как heapsort, обычно предлагают сопоставимую скорость и являются гораздо менее сложными. Кроме того, в отличие от стандартной сортировки слиянием, сортировка слиянием на месте не является стабильной сортировкой. В случае связанных списков алгоритм не использует больше места, чем уже использованное представление списка, но O (log ( k )), используемый для рекурсивной трассировки. Некоторые утверждают, что сортировка связанного списка не имеет места, потому что, даже если вы сортируете в данной структуре данных, структура данных по своей природе содержит O ( n ) дополнительных данных, которыми вы манипулируете (например, ссылки в список).

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

Нет, вам всегда понадобится дополнительная структура данных для объединения отсортированных элементов. Если нет, то вы просто перезаписываете материал, который вы уже отсортировали.