## Search found 9 matches

Fri Mar 02, 2012 5:15 pm UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

Oh right, I forgot about that. Yes, you're right that any arbitrary input is supported, but note that the algorithms become less efficient as the block size differs more from sqrt(n). If you deviate much from sqrt(n), the log-log-linear inplace merge sort will be more efficient. That's interesting....
Fri Mar 02, 2012 4:29 pm UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

Well, the paper doesn't suggest any strategy for the case where all keys have the same value. That's why there is a lower bound of sqrt(n) on the number of distinct key values. There is no way to make it work for fewer distinct key values, AFAIK. That is the catch I was talking about. It seems that...
Fri Mar 02, 2012 2:36 pm UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

The trick is in the composition of the buffer. All keys in the buffer are distinct, and each of the keys was the first of its rank (or the last, depending on which algorithm we're talking about). So when you sort the buffer in the end you don't need to worry about the relative order of the keys wit...
Fri Mar 02, 2012 3:38 am UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

EDIT: So I dived headlong into it, and I found out that it is a merging sort after all (so I was wrong about that). Again there is a catch: the algorithm only works if no key appears more than approximately sqrt(n) times in the array. It's basically a faster version of an algorithm that was already...
Thu Mar 01, 2012 5:12 am UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

Links to the papers (neither should require any special subscriptions): http://comjnl.oxfordjournals.org/content/35/6/643]Huang and Langston 1992 ftp://db.stanford.edu/pub/public_html/cstr.old/reports/cs/tr/74/470/CS-TR-74-470.pdf]Trabb Pardo 1977 Thanks for the links! I shall be reading these over...
Thu Mar 01, 2012 5:11 am UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

Yes, the merge in isolation is linear and the sorting algorithm overall is in-place, O(n log n) and unstable. They state that very clearly in section 5. In section 5 they also claim to have found a non-merging sorting algorithm that is in-place, O(n log n) and stable , but that one is discussed in ...
Tue Feb 28, 2012 2:24 pm UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

dhruvbird is right: this merge algorithm takes linear time while std::inplace_merge takes log-linear time. However there is a catch: this algorithm isn't stable! The authors do claim to have a sorting algorithm (but not a merge algorithm) that is stable, in-place and log-linear though... I'm going ...
Sat Feb 25, 2012 3:34 pm UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

It is possible to merge contiguous chunks of memory (input) in-place in O(n) time. You can read about it here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523 That paper discusses a merge operation that takes O(n log n) operations, just like the algorithm mentioned by lgw. I do thin...
Fri Feb 24, 2012 1:01 am UTC
Forum: Computer Science
Topic: Merging lists in place
Replies: 41
Views: 10571

### Re: Merging lists in place

It is possible to merge contiguous chunks of memory (input) in-place in O(n) time. You can read about it here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523