Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c++ Subject: Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Date: Fri, 10 Jan 2020 13:53:52 -0800 Organization: A noiseless patient Spider Lines: 19 Message-ID: <86k15z3rm7.fsf@linuxsc.com> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="7b070c0766e341d0df2bb5814a4c869f"; logging-data="24031"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX190PugeE+8CstWDhhfTcxNXnEw0EOuRzHU=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:bCsvaDE0vsp0mNxY1ExD6bwJlSY= sha1:v9pirC9EM+w3NAvP8Fgx5Ge0D8Y= Xref: csiph.com comp.lang.c++:71266 Robert Wessel writes: > Generally the O(n**2) sorts are considered usable up a few tens of > items. And use insertion sort, not bubble sort (simpler algorithm, > twice as fast on average). The simplest bubble sort is simpler than the simplest insertion sort. The most complete bubble sort is simpler than the most complete insertion sort. It is only if we compare a somewhat less complete rendition of insertion sort to a somewhat more complete rendition of bubble sort that "insertion sort" may be called simpler. I agree that insertion sort is a better choice than bubble sort in almost all cases, but saying insertion sort is simpler than bubble sort is an apples-and-oranges comparison.