Talk:Dutch national flag problem: Difference between revisions

::The task, as currently written, does not support the idea of balls containing information which is ignored for the purpose of the sort. (For example, imagine a task which asks us to sort numbers in the range 1000..3999 by their most significant digit, preserving the relative order of values with the same leading digit. Or, imagine a task which asks us to generate a variety of random objects and then sort a list of them based on one of their properties.)

::That said, if it did, we could still use the concept of a counting sort. For example, we could replace the counters with stacks -- that would still give us an O(n) algorithm. (Or we could use some mathematically equivalent construct.)

::That said, note that O(n) algorithm does not guarantee O(n) behavior. The cache architecture of modern machines will add a Heaviside step function (of n, where n is the amount of memory used) to the time needed for the algorithm to complete. And, typical OS (and memory management) infrastructure will add random noise to this time. --[[User:Rdm|Rdm]] 13:22, 2 July 2012 (UTC)