|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
16 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
A Provably, Linear Time, In-place and Stable Merge Algorithm via the Perfect Shuffle | | John Ellis
; Ulrike Stege
; | | Date: |
3 Aug 2015 | | Abstract: | We reconsider a recently published algorithm (Dalkilic et al.) for merging
lists by way of the perfect shuffle. The original publication gave only
experimental results which, although consistent with linear execution time on
the samples tested, provided no analysis. Here we prove that the time
complexity, in the average case, is indeed linear, although there is an
Omega(n^2) worst case. This is then the first provably linear time merge
algorithm based on the use of the perfect shuffle. We provide a proof of
correctness, extend the algorithm to the general case where the lists are of
unequal length and show how it can be made stable, all aspects not included in
the original presentation and we give a much more concise definition of the
algorithm. | | Source: | arXiv, 1508.0292 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER