Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A Memory-Adaptive Merge Algorithm?

Tags:

Many algorithms work by using the merge algorithm to merge two different sorted arrays into a single sorted array. For example, given as input the arrays

1  3  4  5  8 

and

2  6  7  9 

The merge of these arrays would be the array

1  2  3  4  5  6  7  8  9 

Traditionally, there seem to be two different approaches to merging sorted arrays (note that the case for merging linked lists is quite different). First, there are out-of-place merge algorithms that work by allocating a temporary buffer for storage, then storing the result of the merge in the temporary buffer. Second, if the two arrays happen to be part of the same input array, there are in-place merge algorithms that use only O(1) auxiliary storage space and rearrange the two contiguous sequences into one sorted sequence. These two classes of algorithms both run in O(n) time, but the out-of-place merge algorithm tends to have a much lower constant factor because it does not have such stringent memory requirements.

My question is whether there is a known merging algorithm that can "interpolate" between these two approaches. That is, the algorithm would use somewhere between O(1) and O(n) memory, but the more memory it has available to it, the faster it runs. For example, if we were to measure the absolute number of array reads/writes performed by the algorithm, it might have a runtime of the form n g(s) + f(s), where s is the amount of space available to it and g(s) and f(s) are functions derivable from that amount of space available. The advantage of this function is that it could try to merge together two arrays in the most efficient way possible given memory constraints - the more memory available on the system, the more memory it would use and (ideally) the better the performance it would have.

More formally, the algorithm should work as follows. Given as input an array A consisting of two adjacent, sorted ranges, rearrange the elements in the array so that the elements are completely in sorted order. The algorithm is allowed to use external space, and its performance should be worst-case O(n) in all cases, but should run progressively more quickly given a greater amount of auxiliary space to use.

Is anyone familiar with an algorithm of this sort (or know where to look to find a description of one?)

like image 236
templatetypedef Avatar asked Nov 29 '11 01:11

templatetypedef


People also ask

Is merge sort an adaptive algorithm?

Merge Sort is a comparison based sorting algorithm with O(n log n) computational complexity. It is not adaptive to existence of ordering among the elements. Thus, has the same computational complexity in any case.

Why merge sort is adaptive?

Adaptive Merge Sort performs the merging of sorted sub-list merge sort does. However, the size of initial sub-list is depended upon the existence of ordering among the list of elements rather than having sub-list of size 1. For example, consider list in the figure. It consists of 2 sorted sub-lists.

Why merge sort is non adaptive?

For instance, if an array is sorted they will take advantage of the sorted order. According to me, no matter if an array is sorted or not, merge sort will still go in for comparisons and then merge. So, the answer is none of these are adaptive.

What is binary merge?

Binary merge. The binary merge operation is a very common operation in computer science, where two individual sorted sequences are merged into one larger sorted sequence.


2 Answers

at least according to the documentation, the in-place merge function in SGI STL is adaptive and "its run-time complexity depends on how much memory is available". The source code is available of course you could at least check this one.

like image 146
Antti Huima Avatar answered Oct 05 '22 10:10

Antti Huima


EDIT: STL has inplace_merge, which will adapt to the size of the temporary buffer available. If the temporary buffer is at least as big as one of the sub-arrays, it's O(N). Otherwise, it splits the merge into two sub-merges and recurses. The split takes O(log N) to find the right part of the other sub array to rotate in (binary search).

So it goes from O(N) to O(N log N) depending on how much memory you have available.

like image 23
MSN Avatar answered Oct 05 '22 11:10

MSN