What is the c plus plus programme for merge sort without recursion?

Answer 1

The following template function will sort an array of any type using the merge sort algorithm, non-recursively. Note that you must call the function by passing a pointer to the array, rather than passing the array by reference as you normally would with sorting algorithms. This is because the function uses a second array (a work array) of the same size to perform the actual merge, switching from one to the other upon each iteration, so there's no guarantee the final sorted array will be the one you originally referred to (it could be the work array). You could maintain a count of the iterations and perform an extra copy of the work array back to your referenced array if the count is odd, but it's more efficient to simply return the sorted array through a pointer.

The code can be difficult to follow if you're not familiar with the merge sort algorithm, so I've commented the code verbosely to explain what's going on. In essence, we're treating the original array as being several subsets of 1 element each. A subset of 1 is already sorted, so we simply merge these subsets in pairs, so the new array contains sorted subsets of 2 elements each. We repeat the process, merging each pair of subsets to create sorted subsets of 4, then 8 and so on, until there is only 1 sorted subset in the array. When we merge two subsets into one, we simply compare the first element of each subset and place the lowest into the merged subset.

Note that in the final iteration, the second subset of the pair may be smaller than the first, or it may not exist at all (in which case the remaining subset may be smaller). However, the merge algorithm caters for this eventuality quite efficiently. If there's only one subset remaining (which can happen during any iteration as elements are removed from the subsets and merged into the work array), the remaining elements are simply copied sequentially from that subset since they will already be in order (as determined by the previous iteration).

template<typename T>

void merge_sort(T* A[], size_t size)

{

// Arrays of length 0 or 1 are already sorted.

if( size < 2 )

return;

// Instantiate a new array of the same size as A.

T *B = new T[size];

// Array A initially contains subsets of width 1 element, then 2, 4, 8...

for( size_t width=1; width<size; width<<=1 )

{

// Dereference A (now known as C).

T *C = *A;

// Array B initially holds subsets of width 2 elements, then 4, 8, 16...

size_t width2 = 2*width;

// Iterate through each pair of subsets in C...

// sub1 is the start index of the first subset of the pair in C.

for( size_t sub1=0; sub1<size; sub1+=width2 )

{

// sub2 is the start index of the second subset of the pair in C.

size_t sub2 = min( sub1+width, size );

// next is the start of the next pair of subsets in C.

size_t next = min( sub1+width2, size );

// Start with the first elements in each pair of subsets in C

// (the ones with the lowest values in each subset).

size_t c1 = sub1;

size_t c2 = sub2;

// Iterate through B's elements from index [sub1] to index [next-1].

for( size_t b=sub1; b<next; ++b )

// Copy the lowest of the two indexed values in C to B.

B[b] = ( c1<sub2 && ( c2>=next C[c1]<=C[c2] )) ? C[c1++] : C[c2++];

}

// Swap the roles of *A and B (note that C still points to the dereferenced A at this point).

*A=B; B=C;

}

// Finished with B (*A is now the fully-sorted array).

delete[]B;

}