Talk:Sorting algorithm

How bad is this code

template <class iterator> void gnome(iterator first, iterator last){ // O(n^2) iterator pos = first; while (pos <= last) { if ((pos == first) || ((*pos) >= *(pos - 1))) ++pos; else { std::iter_swap(pos, pos+1); --pos; } } }

Slowsort

I'm surprised at not finding slowsort here. While it is one of the less serious kind of algorithms, it is interesting since it is, however slowly, steadily progressing to its goal (as opposed to, say, bogosort). The algorithm:

1. Find the maximum
   1. Find the maximum of the first half
   2. Find the maximum of the second half
   3. Find the largest of those maxima
2. Sort the remainder

It is described at http://c2.com/cgi/wiki?SlowSort and was, according to that page, first published in the satyrical article "Pessimal algorithms and the simplexity of computations" by A. Broder and J. Stolfi, in ACM SIGACT News vol. 16 no. 7, pages 49--53, fall 1984. I haven't located that article yet, though. Both links given there are broken. —Preceding unsigned comment added by SQB (talk • contribs) 20:08, 26 July 2009 (UTC)

Stupid sort

Stupid sort - This article was copied from the deleted Wikipedia article which sat in the "Stupid sort" page. -- A perfect demonstration how stupidity proliferates in the internet with the help and andorsement of wikipedia :-) 23:25, 6 February 2010 (UTC)

Why are worst case time complexities wrong?

For example, the time complexity for bubble sort is listed as n².

While its computational complexity (time + space) is on the order of n² (2n²-2n), the worst case time complexity is not n².

worst case time complexity (comparisons) for bubble sort is (n²/2) - (n/2). But they are all wrong. —Preceding unsigned comment added by 74.140.173.132 (talk) 05:57, 24 February 2010 (UTC)

I don't understand what you say, because Ordo((n²/2) - (n/2)) = Ordo(n²). Any term less than n² is overshadowed by n², and the constant 1/2 is irrelevant. The complexity is a scalability function when the function compares to itself dealing with increasingly huge arrays. Rursus dixit. (^mbork³!) 19:48, 6 July 2010 (UTC)

the wrong is the thing —Preceding unsigned comment added by 203.110.243.22 (talk) 12:07, 20 November 2010 (UTC)

There is nothing wrong with worst case time complexitiy

(n²/2) - (n/2) IS O(n²)

Missing O()?

Should it be O(n log n) instead n log n in comparison table? —Preceding unsigned comment added by Conan (talk • contribs) 00:06, 9 May 2010 (UTC)

Quick sort error

Comparison table states that its "memory" is log(n). But, as far as I know, quick sort is in-place sort. Even its own article said so: "...Coupled with the fact that quicksort is an in-place sort and uses no temporary memory...". —Preceding unsigned comment added by 85.222.169.174 (talk) 13:44, 4 June 2010 (UTC)

As it says later in the quicksort article, memory is required for the stack frames which are implicit in the recursion. "No temporary memory" is just wrong. 67.162.90.113 (talk) 19:59, 2 November 2010 (UTC)

Randomized Quiz Sort Algorithm

In the worst case, quicksort sorts a group of items in O(N2), where N is the number of items. If randomization is incorporated into the algorithm, however, the chances of the worst case actually occurring become diminishingly small, and on average, quicksort has a runtime of O(N*Log(N)). Other algorithms guarantee a runtime of O(N*Log(N)), even in the worst case, but they are slower in the average case. Even though both algorithms have a runtime proportional to N*Log(N), quicksort has a smaller constant factor - that is it requires C*N*Log(N) operations, while other algorithms require more like 2*C*N*Log(N) operations —Preceding unsigned comment added by Tarun telang (talk • contribs) 10:31, 11 June 2010 (UTC)

"Comparison of algorithms" table ordering

I find it rather ironic that this table does itself not appear to be sorted! The "exchanging" methods are kept together and are ordered alphabetically, but other than that the order seems to be pretty random. I am in favour of sorting this table according to Method and then name, but other options such as by average case complexity and then name also seem fine to me. It may be like a bit of a plug that Timsort has been placed at the top of this table. There seems to be less reason for it to appear in the table compared to some algorithms that are currently omitted.

Secondly, I'd also like to see a best case column added to the table. Then it would make sense to add other algorithms such as Binary Insertion Sort whose best case differs from normal Insertion Sort, but the average and worst cases are the same. It would also make sense to hilight the fact that bubble sort (amoung others) can be implemeneted with an O(n) best case. Several other algorithms such as Bitonic Merge Sort, Bingo Sort, Odd-Even Transposition Sort, Strand Sort, Squeeze Sort, and Order Sort to name a few, could also be added.

Malcolm —Preceding unsigned comment added by 118.92.109.220 (talk) 03:01, 13 June 2010 (UTC)

Issues with attached file: SortingAlgoComp.png

The linked file "File:SortingAlgoComp.png" has a very poor quality of information. There are some spelling mistakes "Tourament" (missing 'n') and "Interger" (extra 'r') The description states: "This chart shows the complexity of different algorithms when sorting one million integers (from 1 to 1000).". However it is not clear where these numbers come from. Are they comparison counts? Are they swap (or assignment) counts? A combination of both of these measures? What was the initial ordering of the data? Over how many runs were these numbers averaged? How is it that so many of the algorithms all have exactly 1.99316x10^7 as the count? What does "Sorting networks" mean in this picture, and how is the result for it able to not be a whole number? How was bogosort measured given the ridiculously high number shown?

I believe that in its current form, this image adds no value to the article and should be removed. If the information is to be explained and kept then it should converted to a textual form instead.

Malcolm 118.92.109.220 (talk) 04:45, 13 June 2010 (UTC)

Fixing a lede sentence

This sentence makes no sense to me: "Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly." I can't fix it because I don't know what it's trying to say. So I'm inviting others to work on this. If no fix is forthcoming, I will likely delete this sentence.

By the way, it might be helpful in the summary of each algorithm to describe its performance on various types of datasets (e.g., random, nearly sorted, reversed, few unique elements). MichaelBluejay (talk) 12:56, 22 June 2010 (UTC)

Are sorting networks truly stable sorts?

A simple sorting network consisting of four wires and five connectors

Consider this sorting network as included in the Sorting network article. Let's put [2, 1a, 1b, 0] on the wires with 'a' and 'b' as markers for the initial order without them belonging to the sorting key. If this sorting network is stable, we can expect it to return [0, 1a, 1b, 2]. The way I see it, it just doesn't:

2, 1a, 1b, 0 is the initial configuration.
1b, 1a, 2, 0 results from the first comparison. 2 > 1, thus we swap.
1b, 0, 2, 1a results from the second comparison. 1 > 0, thus we swap.
0, 1b, 1a, 2 results from the next two comparisons. We swap both since 1 > 0 and 2 > 1.
0, 1b, 1a, 2 is the result. No swap in the last comparison since 1 = 1.

However, [0, 1b, 1a, 2] does not equal [0, 1a, 1b, 2], which was our expected result. From this counterexample follows that sorting networks are not stable sorts in the general case.

So… am I missing anything here? —Preceding unsigned comment added by 129.13.72.197 (talk) 11:23, 23 June 2010 (UTC)

Quantum sort

Quantum sorting is not faster than normal sorting (http://arxiv.org/abs/quant-ph/0102078) but might offer better time-space tradeoffs. Thus, Quantum sort does not need to have its own article. I propose merging the brief content from quantum sort into the sorting algorithm article. Comments? Please also comment on the quantum sort talk page so that we can delete that article and incorporate it into this one. --DFRussia (talk) 20:56, 29 June 2010 (UTC)

Bubble sort

The section Bubble sort claims:

This algorithm is highly inefficient, and is rarely used[citation needed], except as a simplistic example.

Looks like false to me. Because of the code brevity of the algorithm, it instead should be heavily used on pretty short lists in naive Q&D implementations where a sort is needed. Also it is often combined with quicksort and quickersort for when the to-be-sorted sublists are under a certain length, such as 3 or 4 elements. This use to improve the sorting speed. So the statement is dubious. Rursus dixit. (^mbork³!) 19:57, 6 July 2010 (UTC)

I don't think that's true. If quick & dirty is required, one can implement Quicksort in a single line as in [1]. For sorting of short sub-lists, I have observed variants on Insertion sort much more often than Bubble sort. For the case of finite lengths on those sub-lists, optimal compare-and-swap sequences are known for lists with a maximum length of at least 47 items, probably more. I think there's even a sequence on Sloane's for that, can't seem to find it right now. —Preceding unsigned comment added by 129.13.72.197 (talk) 16:17, 10 July 2010 (UTC)

Joshua Kehn blog

Is this sorting demo page an external link that should or should not be included in the article. Baltar, Gaius (talk) 05:06, 6 January 2011 (UTC)

Discussion on this sorting algorithm page and its inclusion in the external links section.

I have undone the addition of this link because, IMO, it is blatant self promotion. Furthermore, I and at least one other editor report problems with the animations there crashing or hanging for substantial periods of time. Reyk _YO! 06:48, 10 October 2010 (UTC)

Seeing as this section was already there

If you want to include the links, bring the subject up on the article's talk page. Supply links to the existing discussion. State why you think the links are appropriate for WP. I'd like to see your argument why WP should tolerate links that hang a user's browser or denigrate the use of IE.

I believe these links are appropriate for WP because currently there is not enough diversity in the existing examples. You have one that constrains a viewer to a having the JRE installed, and another is non-interactive through the use of animated GIFs. From this StackOverflow question I found this sorting demo page.

The sorting demo is built on open standards, using HTML5's canvas (with support for IE) and JavaScript to display an interactive animated sort. This demo is compatible with almost all browsers and operating systems, including support for mobile devices such as Apple's iPhone, iPod, iPad and other mobile devices (namely Android based). Open standards allow for community improvement and investigation, rather then simply seeing a few bars move you can download the source and research it yourself. While I will concede that this is less of an issue in sort algorithms that have publicly implementations, it is a good path to follow and more conducive to student learning purposes.

In regards to the hanging a user's browser I find no issue with it. If you do then I'm sure contacting the author with more specific details will yield a fix. As far as denigrating the use of Internet Explorer, the most offensive statement I could find is as follows:

: IE users will notice a overall sluggishness due to IE not implementing native <canvas> support. You have my sympathies. 

Internet Explorer does not have native canvas support, and the author supports this browser through the use of a excanvas plugin that will reduce the speed at which the animation can be displayed.

Baltar, Gaius (talk) 20:17, 2 December 2010 (UTC)

• Oppose. The site is anti-IE - a stance that WP should avoid. Suggesting that people switch browsers is not reasonable. The requested EL has crashed other browsers. Author states bubble sort will cause browsers to go to lunch for a while. That other demos have problems/requirements does not justify including this one; two wrongs don't make a right. I have a HUGE ISSUE with the notion that a WP user follows a link and his browser locks up. We should not direct people to bad implementations. Despite JK's good intentions, we are not a source of β-testers. Glrx (talk) 21:14, 2 December 2010 (UTC)

Suggesting that a user support standards compliant browsers is reasonable, and the fact that extra effort seems to be made to support Internet Explorer should be noted. The Author states Some sorts (bubble) are particularly intensive and not recommended for older / slower computers., not that will cause browsers to go to lunch for a while. There is a momentary stall considering the large amount of pre-computation required to smoothly render the bubble sort. Considering the source (JavaScript) one can assume that the browsers with faster JavaScript engines will perform better, this is not bias but rather pertinent information.

The argument that other demos have gaps means this one should not isn't valid. This demo is filling gaps left by others, and as such plays a vital role in offering the most options to users. Suggesting that this is beta software is incorrect. Baltar, Gaius (talk) 14:56, 6 December 2010 (UTC)

Continuing. If there are not more opposed I would like inclusion of this link. Baltar, Gaius (talk) 14:56, 6 December 2010 (UTC)

It does not work that way. You want to add some challenged material, so you must garner a WP:Consensus to make that addition. You don't have a consensus. Furthermore, others have reverted the links. Glrx (talk) 16:27, 6 December 2010 (UTC)

Can you explain what issues you still have? I believe the anti-IE and crashing browsers have both been explained unless you have other issues you would like to bring up. Baltar, Gaius (talk) 19:35, 6 December 2010 (UTC)

I would appreciate at least a semblance of discussion. If you could explain what other issues you have I would like a chance to debate them. One other person reverted the link, I don't see that as a consensus. There are two people in a discussion, how do we involve more? — Preceding unsigned comment added by Baltar, Gaius (talk • contribs) 14:20, 13 December 2010 (UTC)

Support inclusion - In my opinion, it is a highly helpful link which will help users visualize the process of sorting algorithms. I just ran it on IE, and it worked just fine (albeit slower than on FireFox). Reaper Eternal (talk) 02:55, 21 December 2010 (UTC)

I also had to remove the 3O template since three editors: Baltar, Gaius (talk · contribs), Glrx (talk · contribs), and Reyk (talk · contribs) are already involved. 3O requires that only two editors be involved in the dispute. I have, however, offered my opinion on the matter above. Reaper Eternal (talk) 03:00, 21 December 2010 (UTC)

My mistake, I forgot Template:Reyk was included. Baltar, Gaius (talk) 05:34, 21 December 2010 (UTC)

• Weak oppose- I agree with Glrx that we should not be directing people to implementations of sorting algorithms that can hang the browser. I am no longer so concerned about denigrating IE; the warning against it is actually rather mild. Reyk _YO! 22:28, 22 December 2010 (UTC)

What sorts have you found that hang the browser? Baltar, Gaius (talk) 02:33, 23 December 2010 (UTC)

Bubble sorts at full size cause Firefox to hang for a while. Ztothefifth (talk) 02:47, 23 December 2010 (UTC)

Basically this. I have sometimes seen the bubble sort at full size grind to a halt and not recover at all, forcing me to shut it down in task manager, though it usually does right itself eventually. I also get random five to ten second hangs occasionally with the other algorithms. Not game to even try it with IE. Reyk _YO! 02:59, 23 December 2010 (UTC)

To be fair there is a warning before doing a full sized bubble sort. The default sort set is significantly smaller then a full sized set. Baltar, Gaius (talk) 14:31, 23 December 2010 (UTC)

What other links to animations are there? All I see is http://www.sorting-algorithms.com/. Ztothefifth (talk) 18:50, 23 December 2010 (UTC)

Another possible link is http://sortvis.org/. Ztothefifth (talk) 21:06, 23 December 2010 (UTC)

As far as I know there are not many sorting demo's out there, let along interactive ones such as this, which is why I'm pushing strongly for inclusion. Most of the demos are simple. Either pictures or animated gifs. The few more complex ones are applets designed to only run one sort with a specific set – essentially no better then an animated gif. This demo is highly interactive and adjustable. Baltar, Gaius (talk) 01:10, 24 December 2010 (UTC)

Attempting Consensus Can we concede that this page offers a interactive sort visualization that is not tied to any platform or operating system requirements, promoting open standards, and has minor stability problems on few platforms? If we can, I believe that inclusion is supported. Baltar, Gaius (talk) 15:18, 4 January 2011 (UTC)

No, there is not a consensus for inclusion. Glrx (talk) 17:37, 4 January 2011 (UTC)

What are your requirements for consensus? I would like to work with you to agree on a point where this link can be included. I will contact the author and see if there is anything he is willing to change or alter that would better encourage a consensus. Does anyone else have points (for or against) that they would like to bring up? Baltar, Gaius (talk) 18:29, 5 January 2011 (UTC)

You could also open a request for comment on this article to get more opinions. Reaper Eternal (talk) 19:12, 5 January 2011 (UTC)

Thank you, I have done so. Baltar, Gaius (talk) 03:35, 6 January 2011 (UTC)

Strong Support These arguments are ridiculous; if you run IE, you should not expect anything to work IMO. But jokes aside, this is a great visualization of sorting algorithms that can help the reader understand the differences. In many cases, and especially so with our CS articles, the articles are too technical (for the average reader), involving runtime complexity, which data structures the algorithms are best implemented in, etc. As a Computer Scientist, I understand these are invaluable to the article. However, they are not "newbie friendly" at all. This provides a great top-level introductory view of sorting algorithms. Also, W/R/T to the larger demos taking longer to pre-process, I think that is a fine and normal limitation. To be honest, I'm surprised that such a trivial "inconvenience" perhaps really outweighs the benefit of deeper understanding of algorithms. Sheesh. jheiv ^{talk contribs}

Update: I ran this on IE and didn't experience any noticeable slowness. I have a pretty decent setup though, so that may explain the difference. My guess is that the warning is just there as a courtesy for users who have slowers computers and run IE. Certainly this is not a bad thing... jheiv ^{talk contribs} 01:40, 7 January 2011 (UTC)

Glrx I would like to come to a consensus with you before adding the link back in. I would ask that you list any remaining objections to inclusion. This has been dragged on long enough. Baltar, Gaius (talk) 18:43, 7 January 2011 (UTC)

You don't come to a WP:Consensus with me; that is something that happens with a group of editors. I clearly oppose the addition. I have stated reasons to support that position. Although I have some other objections, I don't believe they are worth going into right now.

Normally, the primary disputants don't declare a consensus; they let others do that to avoid the appearance of bias. This discussion started a long time ago, nobody declared a consensus, and the matter sort of died on its own. You keep trying to revive it with the hope of a different result. That's OK, but the landscape hasn't changed. If I read between the lines, User:Reaper Eternal believes there was not a consensus for inclusion because he suggested a RFC.

I'm opposed; it hung my IE browser. There have been some improvements, but I remain opposed. My take is that WP should not link to sites where the user can get into trouble. I don't expect the average WP reader to be sophisticated about using websites or avoiding trouble. Certainly, somebody learning about computing complexity for the first time may not appreciate the implications of sorting parameters. User:Reyk has voiced opposition and noted the simulations also hung Firefox. Reyk has moderated that position somewhat, but Reyk reports "random five to ten second hangs" with other simulations. Reyk is understandably reluctant to attempt viewing the simulations in IE. User:Ztothefifth hasn't declared either way, but Ztothefifth has confirmed the bubble sort causes "Firefox to hang for a while". (Ztothefifth's query about other simulations out there suggests he is reluctant to include the link.)

You are coming across as strong advocate for Joshua Kehn. That position troubles me. Instead of addressing the stability issues, you want to overlook them as "minor stability problems on a few platforms". Your statement that the JK link "promot[es] open standards" is irrelevant to this discussion; it suggests you support an agenda to get browser suppliers to support certain open standards. I don't think that is a goal of WP, and WP should not directing its users to sites with the hope they will complain about the limitations of their current browser or switch to a different browser. User:Reaper Eternal has voiced support for the link and did not experience trouble. I wish RE had said more, but that's fine. After the RFC, User:jheiv came in with strong support. Jheiv comes across as dismissive of anything that hangs IE (even with all joking aside), and that would prompt me to give his support little weight. He characterizes the simulations as not "newbie friendly". His second comment comes across as more unbiased.

As it stands, I don't see a consensus. Since the RFC, there's only been one addition for inclusion, and I don't see that addition creating consensus. At this point, with this set of editors, if both Reyk and Ztothefifth were to support inclusion, then I'd be overruled. Even if just one of two supported inclusion, you might have a consensus. If the link were included, I'd put a black box warning warning on it.

Glrx (talk) 21:02, 7 January 2011 (UTC)

PS. See also WP:ELNO numbers 8, 11, and 16. Glrx (talk) 21:20, 7 January 2011 (UTC)

I will address your concerns later this evening. Baltar, Gaius (talk) 21:46, 7 January 2011 (UTC)

First off, WP:ELNO 8 doesn't apply because <canvas> isn't a plugin. 11 doesn't apply because it's a dedicated page, not a personal site or blog. 16 doesn't apply because it is continuously functional, and will remain functional.

Your stated reasons (anti-IE / unstable) have been addressed. The page is not anti-IE. The page is stable. There are conditions that on older machines / inadequate browsers can produce unforeseen problems – but no more so then a Flash plugin crashing or a Applet refusing to load.

My take is that WP should not link to sites where the user can get into trouble. The users aren't getting into trouble. If you believe this is the case, why not remove every link to a Flash enabled or Applet page from WP because there are cases (especially with older machines) where these plugins will cripple a browser.

Certainly, somebody learning about computing complexity for the first time may not appreciate the implications of sorting parameters I agree, and it appears so does the author. The page is set to a default level which produces no reported crashes.

You are coming across as strong advocate for Joshua Kehn. That position troubles me Please enlighten me as to why you are troubled with my position. My position is something worthwhile and decent being so violently opposed by someone for ungrounded reasons.

Your statement that the JK link "promot[es] open standards" is irrelevant to this discussion; it suggests you support an agenda to get browser suppliers to support certain open standards. This may be your take on it but it is not my intent. My intent is to offer an alternative to the current which is widely accepted and in use. Why should there only be an Applet and a set of animated gif's?

I don't think that is a goal of WP, and WP should not directing its users to sites with the hope they will complain about the limitations of their current browser or switch to a different browser Where (anywhere, please) is this implied (by me or JK)? It surely isn't said, so it must be implied.

He characterizes the simulations as not "newbie friendly". He does not. He says In many cases, and especially so with our CS articles, the articles are too technical (for the average reader), involving runtime complexity, which data structures the algorithms are best implemented in, etc.

There is no need for a black box warning given that there is ample warning of any slight instability on the page itself.

I will contact Reyk and Ztothefifth via their talk pages and ask for for them to revisit this. Baltar, Gaius (talk) 02:53, 8 January 2011 (UTC)

• I remain opposed to the addition of this link. I've tested the page on Firefox and it frequently hangs for five to ten seconds regardless of the type of sort or the number of items being sorted. Once or twice it has even caused Firefox to stall completely, forcing me to shut it down in Task Manager. I do not regard this as a "minor instability" but a fairly serious one and I think it would be irresponsible to link to it. Finally I think you're treating the consensus building process as "keep talking and talking until everyone does what I tell them", and that's not how it works. Reyk _YO! 05:23, 9 January 2011 (UTC)

Reyk, can you clarify which options you are using to create these hangs? I can't duplicate this behavior at all, even on my slowest machine. — Preceding unsigned comment added by Baltar, Gaius (talk • contribs) 13:05, 9 January 2011 (UTC)

Oppose crashed or stalled IE8. This is supposed to be an encyclopedia not a soapbox for some pinhead to tell me what software to run on my computer. If you think it is such a brilliant demo turn it into a gif and have done with it.Greglocock (talk) 04:27, 11 January 2011 (UTC)

WP:NPA? Reaper Eternal (talk) 23:11, 11 January 2011 (UTC)

It'd be NPA if the editor promoting the website link, and the website author, were the same person. I referred to the website author as a pinhead. Obviously they cannot be the same person as that would be COI, and we know that the wiki-editor is a man of integrity, not a pinhead, and so would not commit COI, or indeed, pinheadedness. Don't we? Greglocock (talk) 02:21, 12 January 2011 (UTC)

Note that the author ("pinhead") is not telling you what software to run on your computer. In fact, he is telling you that there is very few requirements, namely a browser made in the past five years. The demo running applets is telling you what to run on your computer.

Turning it into a GIF would completely destroy the uniqueness of the demo.

I don't particularly like what you are suggesting, but feel correcting you would be a waste of time. I'm thoroughly disheartened with the Wikipedia editing system now. Such violent opposition to anything new. The slightest (and do I mean slightest, I have only made it crash a handful of times) instability should be grounds for complete removal? Fine. I remain supportive of inclusion if this issue comes up again. Baltar, Gaius (talk) 05:14, 13 January 2011 (UTC)

Bubble sort stability

I think bubble sort is stable (in contrary to what that written in the table) —Preceding unsigned comment added by 79.177.127.22 (talk) 09:55, 2 November 2010 (UTC)

I just reverted some changes that claimed BS stability depends on the implementation. BS should be stable because neighboring elements are not swapped if they are already in order (and two equal elements are in order). Consequently, equal elements will not get out of order. (They can get out of order when non-neighboors are swapped as in Shell short.) Sadly, my statements are WP:NOR, and I don't have a WP:RS citation for BS stability. Glrx (talk) 21:55, 7 November 2010 (UTC)

Log Base

When it says n*log(n) what is the base of the log function? Is it binary (2), decimal (10), natural (e), or some other base? —Preceding unsigned comment added by 69.91.165.139 (talk) 20:04, 15 November 2010 (UTC)

In big O order notation, the base of the logarithm doesn't matter -- log₂, log₁₀, and ln are all related by just a constant. In particular algorithms, there will be a logical base to use: a binary sort would be base 2 and a radix 10 sort would be 10. But again, in terms of big O, the actual base doesn't matter; constant multipliers are discarded. Glrx (talk) 20:49, 15 November 2010 (UTC)

Manual (Physical) Sorting Algorithms

I came looking for assistance in manually sorting tens of thousands of random Election Ballots into a hundred geographic (Precinct) districts. Similarly the Postal Services machine-sort millions of pieces of mail into millions of buckets (zipcodes, routes and addresses). Carrier personnel manually direct-sort their mail into an array of "pigeon-holes" before delivery distribution.

Unfortunately all emphasis here is towards electronic Data-processing. I've got to give these lots of thought to determine applicability to physical-sorts, using physical motions, requiring real-time, and limited buckets within reach or operator constraints. Does EDP sort-theory apply, or have lessons for large physical sorts?

Are info or comments about best physical-sort algorithms appropriate here? What differences apply due to human or mechanical vs electronic/cyber media and speeds? HalFonts (talk) 07:20, 19 November 2010 (UTC)

TimSort

The best case for TimSort should be O(n). It is not just a hybrid mergesort but a hybrid natural mergesort. If the data contains runs that are ordered or reverse ordered or a mixture, then it is between O(n) and O(n * log n). See http://bugs.python.org/file4451/timsort.txt

The same can be said for SmoothSort. If the runs are ordered (but not reverse ordered), then it is O(n). The best cases on these should reflect this. Stephen Howe (talk) 22:39, 25 November 2010 (UTC)

Shell sort

What's happened to this section? Just two curly brackets at the moment. Sam Dutton (talk) 14:01, 26 November 2010 (UTC)

How does it have two different averages? —Tamfang (talk) 07:43, 15 December 2010 (UTC)

Because it is an open problem as to what the asymptotic behaviour of shell sort is. Different gap sequences have different asymptotic behaviour. I will see if better bounds can be found as I believe recent publications by computer theorists have managed to give tighter bounds for shell sort.

Stephen Howe (talk) 21:25, 20 December 2010 (UTC)

Quicksort can be stable?

I dont think this is true, it is only true for quicksort for linked lists. It is not how the pivot is handled, as the article describes, but the fact that all equal elements within the partition set must retain their original order while partitioning. To do so, requires a stable partition (function in C++ library). stable partition requires auxilary memory and cant be done in O(N) without the memory. Any comments?

Stephen Howe (talk) 21:46, 10 December 2010 (UTC)

See Quicksort#Complex version. Glrx (talk) 05:28, 11 December 2010 (UTC)

Thank you. I have seen. But there is nothing on this page that talks about stable partitioning for quicksort. In any case, I think I would have heard something of it. In the past 20 years, Bentley & McIlroy's groundbreaking "Engineering a Sort function" in 1993 introduced 3-way partitioning (sometimes known as "fat pivot") for Quicksort which has also been investigated by Sedgewick See "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8162&rep=rep1&type=pdf" "http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf" which are downloadable PDF's. In terms of partitioning, 2-way partitioning is a maximum of N/2 swaps, for 3-way partitioning (Dutch National Flag problem), it can be as little as ((5 * N) / 9) swaps. But in both cases, neither are stable. It is not pivot element that matters, it is the fact that large blocks of multiple duplicates still retain there original order. I have yet to see stable partioning can be done in O(N) swaps with no auxilary memory. Therefore I motion this reverts to quicksort not being stable unless someone posts URLs to white papers that indicate that recent research indicate that Quicksort can be made stable. NOTE: Quicksort for linked lists can be stable, but I am talking about the array version which I believe this Wiki article addresses.

Stephen Howe (talk) 22:37, 12 December 2010 (UTC)

Perfect Sort / Triangulation Sort

User:Sven nestle2/Perfect Sort / Triangulating Sort Is a fast partitioning sort which hugely excels when hey who's deleting my "fine addition"? please discuss or mail me don't just delete it's a real nuisance.