Нерекурсивная сортировка слиянием

Question

Может кто-нибудь объяснить на английском, как работает нерекурсивная сортировка слиянием?

Спасибо

Answer 1

Нерекурсивная сортировка слиянием работает с учетом размеров окна 1,2,4,8,16..2 ^ n над входным массивом. Для каждого окна ('k' в коде ниже) все смежные пары окон объединяются во временное пространство, а затем помещаются обратно в массив.

Вот моя единственная функция, основанная на C, нерекурсивная сортировка слиянием. Вход и выход находятся в «а». Временное хранение в «б». Однажды я хотел бы иметь версию, которая была на месте:

float a[50000000],b[50000000];
void mergesort (long num)
{
    int rght, wid, rend;
    int i,j,m,t;

    for (int k=1; k < num; k *= 2 ) {       
        for (int left=0; left+k < num; left += k*2 ) {
            rght = left + k;        
            rend = rght + k;
            if (rend > num) rend = num; 
            m = left; i = left; j = rght; 
            while (i < rght && j < rend) { 
                if (a[i] <= a[j]) {         
                    b[m] = a[i]; i++;
                } else {
                    b[m] = a[j]; j++;
                }
                m++;
            }
            while (i < rght) { 
                b[m]=a[i]; 
                i++; m++;
            }
            while (j < rend) { 
                b[m]=a[j]; 
                j++; m++;
            }
            for (m=left; m < rend; m++) { 
                a[m] = b[m]; 
            }
        }
    }
}

Кстати, также очень легко доказать, что это O (n log n). Внешний цикл по размеру окна увеличивается как степень двух, поэтому k имеет log n итераций. Хотя существует много окон, охватываемых внутренним циклом, все окна для данного k точно покрывают входной массив, поэтому внутренний цикл равен O (n). Объединение внутреннего и внешнего циклов: O (n) * O (log n) = O (n log n).

Answer 2

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

Теперь, имея дело с группами из двух групп (любые две, наиболее вероятно смежные группы, но вы можете использовать первую и последнюю группы), объедините их в одну группу, выбирая элемент с наименьшим значением из каждой группы, пока все 4 элемента не будут слились в группу из 4. Теперь у вас есть только группы из 4 плюс возможный остаток. Используя цикл вокруг предыдущей логики, сделайте все это снова, за исключением этой временной работы в группах по 4. Этот цикл выполняется до тех пор, пока не останется только одна группа.

Answer 3

Цитата из Алгоритмист :

Сортировка снизу вверх нерекурсивный вариант слияния сортировать, в котором массив сортируется по последовательность проходов. Во время каждого пройти, массив делится на блоки размером м . (Первоначально m = 1 ). Каждые два соседних блока объединяются (как в обычной сортировке слиянием), и следующий проход сделан с вдвое большим значение м .

Answer 4

Основная причина, по которой вы хотите использовать нерекурсивную сортировку MergeSort, состоит в том, чтобы избежать переполнения стека рекурсии. Я, например, пытаюсь отсортировать 100 миллионов записей, каждая запись длиной около 1 КБ (= 100 гигабайт), в алфавитно-цифровом порядке. Для сортировки по порядку (N ^ 2) потребуется 10 ^ 16 операций, т. Е. Потребуются десятилетия для выполнения даже при 0,1 микросекунде на операцию сравнения. Сортировка слиянием порядка (N log (N)) займет менее 10 ^ 10 операций или менее часа, чтобы работать с той же рабочей скоростью. Однако в рекурсивной версии MergeSort сортировка 100 миллионов элементов приводит к 50 миллионам рекурсивных вызовов MergeSort (). При рекурсии стека в несколько сотен байтов это переполняет стек рекурсии, даже если процесс легко помещается в динамическую память. Выполнение сортировки слиянием с использованием динамически выделяемой памяти в куче. Я использую код, предоставленный Рамой Хетцляйном выше, но я использую динамически выделяемую память в куче вместо использования стека. Я могу отсортировать свои 100 миллионов записей с помощью нерекурсивная сортировка слиянием, и я не переполняю стек. Соответствующий разговор для сайта "Stack Overflow"!

PS: Спасибо за код, Рама Хецляйн.

PPS: 100 гигабайт в куче? !! Ну, это виртуальная куча в кластере Hadoop, и MergeSort будет реализован параллельно на нескольких машинах, распределяющих нагрузку ...

Answer 5

Как рекурсивная, так и нерекурсивная сортировка слиянием имеют одинаковую сложность времени O (nlog (n)). Это связано с тем, что оба подхода используют стек одним или другим способом.

В нерекурсивном подходе пользователь / программист определяет и использует стек

В рекурсивном подходе стек используется системой для хранения адреса возврата функции, которая вызывается рекурсивно

Answer 6

Я новичок здесь. Я модифицировал раствор Рамы Хецляйн (спасибо за идеи). Моя сортировка слиянием не использует последний цикл обратной копии. Плюс это возвращается к сортировке вставки. Я проверил его на своем ноутбуке, и он самый быстрый. Даже лучше, чем рекурсивная версия. Кстати, это в java и сортирует от убывания к возрастанию. И конечно это итеративно. Это можно сделать многопоточным. Код стал сложным. Так что, если кому-то интересно, пожалуйста, посмотрите.

Код:

    int num = input_array.length;
    int left = 0;
    int right;
    int temp;
    int LIMIT = 16;
    if (num <= LIMIT)
    {
        // Single Insertion Sort
        right = 1;
        while(right < num)
        {
            temp = input_array[right];
            while(( left > (-1) ) && ( input_array[left] > temp ))
            {
                input_array[left+1] = input_array[left--];
            }
            input_array[left+1] = temp;
            left = right;
            right++;
        }
    }
    else
    {
        int i;
        int j;
        //Fragmented Insertion Sort
        right = LIMIT;
        while (right <= num)
        {
            i = left + 1;
            j = left;
            while (i < right)
            {
                temp = input_array[i];
                while(( j >= left ) && ( input_array[j] > temp ))
                {
                    input_array[j+1] = input_array[j--];
                }
                input_array[j+1] = temp;
                j = i;
                i++;
            }
            left = right;
            right = right + LIMIT;
        }
        // Remainder Insertion Sort
        i = left + 1;
        j = left;
        while(i < num)
        {
            temp = input_array[i];
            while(( j >= left ) && ( input_array[j] > temp ))
            {
                input_array[j+1] = input_array[j--];
            }
            input_array[j+1] = temp;
            j = i;
            i++;
        }
        // Rama Hoetzlein method
        int[] temp_array = new int[num];
        int[] swap;
        int k = LIMIT;
        while (k < num)
        {
            left = 0;
            i = k;// The mid point
            right = k << 1;
            while (i < num)
            {
                if (right > num)
                {
                    right = num;
                }
                temp = left;
                j = i;
                while ((left < i) && (j < right))
                {
                    if (input_array[left] <= input_array[j])
                    {
                        temp_array[temp++] = input_array[left++];
                    }
                    else
                    {
                        temp_array[temp++] = input_array[j++];
                    }
                }
                while (left < i)
                {
                    temp_array[temp++] = input_array[left++];
                }
                while (j < right)
                {
                    temp_array[temp++] = input_array[j++];
                }
                // Do not copy back the elements to input_array
                left = right;
                i = left + k;
                right = i + k;
            }
            // Instead of copying back in previous loop, copy remaining elements to temp_array, then swap the array pointers
            while (left < num)
            {
                temp_array[left] = input_array[left++];
            }
            swap = input_array;
            input_array = temp_array;
            temp_array = swap;
            k <<= 1;
        }
    }

    return input_array;

Answer 7

На всякий случай, если кто-то еще прячется в этой теме ... Я адаптировал алгоритм нерекурсивной сортировки слиянием Рамы Хетцляйна выше для сортировки двойных связанных списков. Эта новая сортировка на месте, стабильна и позволяет избежать затратного по времени кода разделения списка, который есть в других реализациях сортировки слиянием связанных списков.

// MergeSort.cpp
// Angus Johnson 2017
// License: Public Domain

#include "io.h"
#include "time.h"
#include "stdlib.h"

struct Node {
    int data;
    Node *next;
    Node *prev;
    Node *jump;
};

inline void Move2Before1(Node *n1, Node *n2)
{
    Node *prev, *next;
    //extricate n2 from linked-list ...
    prev = n2->prev;
    next = n2->next;
    prev->next = next; //nb: prev is always assigned
    if (next) next->prev = prev;
    //insert n2 back into list ...  
    prev = n1->prev;
    if (prev) prev->next = n2;
    n1->prev = n2;
    n2->prev = prev;
    n2->next = n1;
}

void MergeSort(Node *&nodes)
{
    Node *first, *second, *base, *tmp, *prev_base;

    if (!nodes || !nodes->next) return;
    int mul = 1;
    for (;;) {
        first = nodes;
        prev_base = NULL;
        //sort each successive mul group of nodes ...
        while (first) {
            if (mul == 1) {
                second = first->next;
                if (!second) { 
                  first->jump = NULL;
                  break;
                }
                first->jump = second->next;
            }
            else
            {
                second = first->jump;
                if (!second) break;
                first->jump = second->jump;
            }
            base = first;
            int cnt1 = mul, cnt2 = mul;
            //the following 'if' condition marginally improves performance 
            //in an unsorted list but very significantly improves
            //performance when the list is mostly sorted ...
            if (second->data < second->prev->data) 
                while (cnt1 && cnt2) {
                    if (second->data < first->data) {
                        if (first == base) {
                            if (prev_base) prev_base->jump = second;
                            base = second;
                            base->jump = first->jump;
                            if (first == nodes) nodes = second;
                        }
                        tmp = second->next;
                        Move2Before1(first, second);
                        second = tmp;
                        if (!second) { first = NULL; break; }
                        --cnt2;
                    }
                    else
                    {
                        first = first->next;
                        --cnt1;
                    }
                } //while (cnt1 && cnt2)
            first = base->jump;
            prev_base = base;
        } //while (first)
        if (!nodes->jump) break;
        else mul <<= 1;
    } //for (;;)
}

void InsertNewNode(Node *&head, int data)
{
    Node *tmp = new Node;
    tmp->data = data;
    tmp->next = NULL;
    tmp->prev = NULL;
    tmp->jump = NULL;
    if (head) {
        tmp->next = head;
        head->prev = tmp;
        head = tmp;
    }
    else head = tmp;
}

void ClearNodes(Node *head)
{
    if (!head) return;
    while (head) {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

int main()
{  
    srand(time(NULL));
    Node *nodes = NULL, *n;
    const int len = 1000000; //1 million nodes 
    for (int i = 0; i < len; i++)
        InsertNewNode(nodes, rand() >> 4);

    clock_t t = clock();
    MergeSort(nodes);    //~1/2 sec for 1 mill. nodes on Pentium i7. 
    t = clock() - t;
    printf("Sort time: %d msec\n\n", t * 1000 / CLOCKS_PER_SEC);

    n = nodes;
    while (n)
    {
        if (n->prev && n->data < n->prev->data) { 
            printf("oops! sorting's broken\n"); 
            break;
        }
        n = n->next;
    }
    ClearNodes(nodes);
    printf("All done!\n\n");
    getchar();
    return 0;
}

Отредактировано 2017-10-27: исправлена ​​ошибка, затрагивающая нечетные списки