Jump to content

Talk:Library sort

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Input randomization required?

[edit]

Arvindn recently edited the claim:

Like the insertion sort it is based on, library sort is a stable comparison sort and can be run as an online algorithm.

to:

Unike the insertion sort it is based on, library sort is not stable and cannot be run as an online algorithm because it requires randomly permuting its input.

As far as i understand it, although the authors do their complexity analysis in the context of randomized input permutations, the algorithm itself doesn't require randomization. Rather, in practice, the situation is similar to quicksort, where optional randomization greatly reduces the probability of pathological inputs, but is not required for good performance with "typical" inputs.

Arvindn, if i'm mistaken, can you please explain? --Piet Delport 23:07, 16 April 2006 (UTC)[reply]

Algorithm?

[edit]

There is no algorithm here, the paper explaining this sort is behind an academic paywall and google can't find it either. Is it even worth mentioning if it's such a secret? — Preceding unsigned comment added by 203.129.26.202 (talk) 16:17, 10 November 2011 (UTC)[reply]


The paper seems to be available now from the links in the article. But I do think there were some gaps (no pun intended) in the given algorithms. Mainly I would like to know how the gaps are meant to be created in the rebalance step, how much memory that is needed apart from the "epmty slots" and how the "brute force binary search" works efficiently when there are gaps in the array.

I looked for implementations on the web, but from what I saw actually the <A href="http://en.wiki.x.io/w/index.php?title=Library_sort&diff=391226317&oldid=371527723">implementation removed from the wp article</A> is the only one that looks like a try. Is there any well done and tested implementation that can be referred to in the external link section?

Is this of real value for real world, or is it academic paper only? JAGulin (talk) 21:06, 9 March 2013 (UTC)[reply]

C and Python code removed

[edit]

I removed the C and Python code and put in a piece of pseudocode instead. The C code in particular was impossible to read, mixed C and C++, mixed the algorithm and I/O code in the main function, had an arbitrary constant for the queue and used a hack that relies on UB to swap elements. Such code does not belong in Wikipedia, nor anywhere else. QVVERTYVS (hm?) 13:49, 30 December 2013 (UTC)[reply]

Retrieved from "http://en.wiki.x.io/w/index.php?title=Talk:Library_sort&oldid=1203585282"