login/register

Snip!t from collection of Alan Dix

see all channels for Alan Dix

Snip
summary

Abstract: Two in-place variants of the classical mergeso... analysed in detail. The first, straightforward variant p... log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves... elements. The second, more advanced variant requires at ... O(N ) compa

Practical In-Place Mergesort - Katajainen, Pasanen, Teuhola (ResearchIndex)
http://citeseer.ist.psu.edu/katajainen96practical.html

Categories

/Channels/AVL trees

[ go to category ]

For Snip

loading snip actions ...

For Page

loading url actions ...
Abstract: Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves to sort N elements. The second, more advanced variant requires at most N log 2 N + O(N ) comparisons and "N log 2 N moves, for any fixed " ? 0 and any N ? N ("). In theory, the second one is superior to advanced versions of heapsort. In practice, due to the overhead in the index manipulation, our...

HTML

<b>Abstract:</b> Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves to sort N elements. The second, more advanced variant requires at most N log 2 N + O(N ) comparisons and "N log 2 N moves, for any fixed " ? 0 and any N ? N ("). In theory, the second one is superior to advanced versions of heapsort. In practice, due to the overhead in the index manipulation, our...

Search Alan Dix Snips

Channels - Alan Dix