Non-recursive merge sort

Question

Can someone explain in English how non-recursive merge sorting works?

thank

Answer 1

Scroll through the elements and make each adjacent group of two sorted ones by replacing them when necessary.

Now, dealing with groups of two groups (any two, the most likely adjacent groups, but you can use the first and last groups) to combine them into one group, selecting the element with the lowest value from each group until all 4 elements are combined into group of 4. Now you have only groups of 4 plus a possible balance. Using the loop around the previous logic, do it all over again, except that this time works in groups of 4. This loop works until there is only one group.

Answer 2

Non-recursive merge sort considering window sizes 1,2,4,8,16..2 ^ n over the input array. For each window (“k” in the code below), all adjacent pairs of windows are merged into temporary space and then returned to the array.

Here is my only function, C-based, non-recursive merge sort. Entrance and exit are in 'a'. Temporary storage in 'b'. One day, I would like to have a version that was in place:

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]; } } } } 

By the way, it is also very easy to prove that it is O (n log n). The outer loop over the window size grows as the power of two, so k has log n iterations. While there are many windows covered by the inner loop, together, all the windows for a given k exactly cover the input array, so the inner loop is O (n). Combining internal and external loops: O (n) * O (log n) = O (n log n).

Answer 3

Quote from Algorithmist :

Bottom-up merge sort is a non-recursive merge sort, in which the array is sorted by a sequence of passes. During each pass, the array is divided into blocks of size m. (Initially m = 1). Every two adjacent blocks are combined (as in a regular merge sort), and the next pass is done with a doubled value of m.

Answer 4

Both recursive and non-recursive merge sort have the same complexity O (nlog (n)). This is because both approaches use the stack in one way or another.

In a non-recursive approach, the user / programmer defines and uses the stack

In the recursive approach, the stack is used inside the system to store the return address of a function called recursively

Answer 5

The main reason you want to use non-recursive MergeSort is to avoid recursion. For example, I am trying to sort 100 million records, each record about 1 kB in size (= 100 gigabytes), in alphanumeric order. The sort of order (N ^ 2) will occupy 10 ^ 16 operations, i.e. For comparison, one operation will take only ten minutes. The (N log (N)) Merge Sort order will take less than 10 ^ 10 operations or less than an hour to operate at the same operating speed. However, in the recursive version of MergeSort, 100-millimeter sorting of elements results in 50-million recursive calls to MergeSort (). In a few hundred bytes for recursion on the stack, this overflows the recursion stack, although the process easily fits into heap memory. Perform merge sorting using dynamically allocated heap memory. I use the code provided by Rama Hetzlein above, but I use dynamically allocated memory on the heap instead of using the stack. I can sort my 100 million records using non-recursive merge sort, and I do not overflow the stack. Appropriate conversation for the Stack Overflow website!

PS: Thanks for the code, Rama Hetzlein.

PPS: 100 gigabytes per heap? !! Well, this is a virtual heap on a Hadoop cluster, and MergeSort will be implemented in parallel on several machines sharing the load ...

Answer 6

I'm new here. I changed the decision of Rama Hoetzlein (thanks for the ideas). My merge sort does not use the last reverse copy loop. Plus it goes back to sorting the insert. I compared it on my laptop and it is the fastest. Even better than the recursive version. By the way, it is in java and sorted in descending order in ascending order. And of course, this is iterative. It can be made multithreaded. The code has become complicated. Therefore, if anyone is interested, please take a look.

The code:

  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

Just in case, someone is still hiding in this thread ... I used the Rama Hoetzlein non-recursive merge sort algorithm above to sort the double linked lists. This new view is in place, stable, and avoids the costly redistribution of code in other code that merges adjacent lists into merge sort implementations.

 // 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 broken\n"); break; } n = n->next; } ClearNodes(nodes); printf("All done!\n\n"); getchar(); return 0; } 

Edited 2017-10-27: Fixed bug affecting lists with odd numbers

Answer 8

I wrote the following code snippet from scratch with pretty basic knowledge.

This is my interpretation of how iterative merge sort should work:

1. Keep the array in half until a mass of individual elements is gathered;

2. Take one array of elements in a pair and combine them until there is only one array.

 function mergeSort(array) { let len = array.length let list = [array] while (true) { // keep halving array until there a moltitude of single item arrays for (let i = list.length - 1; i > -1; i--) { list.push(...halve(...list.splice(i, 1))) } if (list[0].length < 2) { break } } // take single item arrays in pair and merge-sort them until there only one array while (true) { for (let i = list.length - 1; i > 0; i -= 2) { list.push(merge(...list.splice(i-1, 2))) } if (list[0].length === len) { return list[0] } } return list } // halving happens here function halve(array) { let n = array.length if (n < 2) { return [array] } let left = array.slice(0, n/2|0) let right = array.slice(n/2|0) if (left.length > right.length) { return [left, right] } return [right, left] } // merging happens here function merge(left, right) { let merged = [] // result array to return let i = 0 let j = 0 while ( i < left.length && j < right.length ) { // choose the smallest from the two if ( left[i] <= right[j] ) { merged.push( left[i] ) i++ } else { merged.push( right[j] ) j++ } } // push all the left-over while( left[i] ) { merged.push( left[i] ) i++ } while( right[j] ) { merged.push( right[j] ) j++ } return merged } console.log(mergeSort([3,2,6,9,3,7,4,5,8,1,1]))