Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It's important to note that an algorithm that is <code>O(N log N)</code> is not always faster in practice than an <code>O(N^2)</code> algorithm. It depends on the constants, and the range of <code>N</code> involved. (Remember that <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow noreferrer">asymptotic notation</a> measures relative growth rate, not absolute speed).</p> <p>For small <code>N</code>, insertion sort in fact does beat merge sort. It's also faster for almost-sorted arrays.</p> <p>Here's <a href="http://www.sorting-algorithms.com/insertion-sort" rel="nofollow noreferrer">a quote</a>:</p> <blockquote> <p>Although it is one of the elementary sorting algorithms with <code>O(N^2)</code> worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).</p> <p>For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.</p> </blockquote> <p>Here's another quote from <a href="http://portal.acm.org/citation.cfm?doid=359024.359026" rel="nofollow noreferrer"><em>Best sorting algorithm for nearly sorted lists</em></a> paper:</p> <blockquote> <p>straight insertion sort is best for small or very nearly sorted lists</p> </blockquote> <p>What this means is that, in practice:</p> <ul> <li>Some algorithm <em>A<sub>1</sub></em> with higher asymptotic upper bound may be preferable than another known algorithm <em>A<sub>2</sub></em> with lower asymptotic upper bound <ul> <li>Perhaps <em>A<sub>2</sub></em> is just too complicated to implement</li> <li>Or perhaps it doesn't matter in the range of <code>N</code> considered <ul> <li>See e.g. <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="nofollow noreferrer">Coppersmith–Winograd algorithm</a></li> </ul></li> </ul></li> <li>Some hybrid algorithms may adapt different algorithms depending on the input size</li> </ul> <h3>Related questions</h3> <ul> <li><a href="https://stackoverflow.com/questions/1513566/which-sorting-algorithm-is-best-suited-to-re-sort-an-almost-fully-sorted-list">Which sorting algorithm is best suited to re-sort an almost fully sorted list?</a></li> <li><a href="https://stackoverflow.com/questions/736920/is-there-ever-a-good-reason-to-use-insertion-sort">Is there ever a good reason to use Insertion Sort?</a></li> </ul> <hr> <h3>A numerical example</h3> <p>Let's consider these two functions:</p> <ul> <li><code>f(x) = 2x^2</code>; this function has a quadratic growth rate, i.e. "<code>O(N^2)</code>"</li> <li><code>g(x) = 10x</code>; this function has a linear growth rate, i.e. "<code>O(N)</code>"</li> </ul> <p>Now let's plot the two functions together:</p> <p><img src="https://i.stack.imgur.com/2IxL5.gif" alt="alt text"><br> <sup><em>Source:</em> <a href="http://www.wolframalpha.com/input/?i=plot+2x%5E2+and+10x+for+x+from+0+to+10" rel="nofollow noreferrer">WolframAlpha: <code>plot 2x^2 and 10x for x from 0 to 10</code></a></sup></p> <p>Note that between <code>x=0..5</code>, <code>f(x) &lt;= g(x)</code>, but for any larger <code>x</code>, <code>f(x)</code> quickly outgrows <code>g(x)</code>.</p> <p>Analogously, if <em>A<sub>1</sub></em> is a quadratic algorithm with a low overhead, and <em>A<sub>2</sub></em> is a linear algorithm with a high overhead, for smaller input, <em>A<sub>1</sub></em> may be faster than <em>A<sub>2</sub></em>.</p> <p>Thus, you can, should you choose to do so, create a hybrid algorithm <em>A<sub>3</sub></em> which simply selects one of the two algorithms depending on the size of the input. Whether or not this is worth the effort depends on the actual parameters involved.</p> <p>Many tests and comparisons of sorting algorithms have been made, and it was decided that because insertion sort beats merge sort for small arrays, it was worth it to implement both for <a href="http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort%28java.lang.Object[]%29" rel="nofollow noreferrer"><code>Arrays.sort</code></a>.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhy does java.util.Arrays.sort(Object[]) use 2 kinds of sorting algorithms?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USpolygenelubricants
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhy does java.util.Arrays.sort(Object[]) use 2 kinds of sorting algorithms?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou may like to compare the graph above with some actual measurements I took between an insertion sort and Java's sort: http://www.javamex.com/tutorials/collections/sorting_java_algorithm_performance_2.shtml
      singulars
      1. PO
      1. USNeil Coffey
    2. COIn addition to this excellent analysis, note that there are _two different kinds_ of insertion sort commonly used--the regular one and "binary insertion sort" where you find the spot to insert into by binary search, and then shift everything to make space. On most processors these days, a swap is faster than a compare, and binary insertion sort reduces the number of compares. Thus, usually, under the hood you'll find a binary insertion sort.
      singulars
      1. PO
      1. USRex Kerr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload