Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This change went through the <a href="http://mail.openjdk.java.net/pipermail/core-libs-dev/" rel="nofollow noreferrer">core-libs mailing list</a> when it went in so there is some discussion and useful links there. Here's the <a href="http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/" rel="nofollow noreferrer">web rev</a> with code review changes and also the <a href="http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/timsort.patch" rel="nofollow noreferrer">original patch</a>.</p> <p>The comments in the code say:</p> <blockquote> <p>Implementation note: This implementation is a stable, adaptive,<br> iterative mergesort that requires far fewer than n lg(n) comparisons<br> when the input array is partially sorted, while offering the<br> performance of a traditional mergesort when the input array is<br> randomly ordered. If the input array is nearly sorted, the<br> implementation requires approximately n comparisons.<br> Temporary storage requirements vary from a small constant for nearly sorted<br> input arrays to n/2 object references for randomly ordered input<br> arrays. </p> <p>The implementation takes equal advantage of ascending and<br> descending order in its input array, and can take advantage of<br> ascending and descending order in different parts of the the same<br> input array. It is well-suited to merging two or more sorted arrays:<br> simply concatenate the arrays and sort the resulting array.<br> The implementation was adapted from Tim Peters's list sort for Python<br> <a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt" rel="nofollow noreferrer">TimSort</a>. It uses techiques from Peter McIlroy's "Optimistic<br> Sorting and Information Theoretic Complexity", in Proceedings of the<br> Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,<br> January 1993. </p> </blockquote> <p>Buried in there is the <a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt" rel="nofollow noreferrer">very useful link to the Python implementation details</a>, and I think that's a great place to start, followed by the code. To be incredibly high level about it, timsort improves performance by noticing runs of sorted data and taking advantage of that structure during the sort.</p>
    singulars
    1. This table or related slice is empty.
    1. POGrokking Timsort
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAndy Mikula
    1. USAlex Miller
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    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. COI actually meant to link to that in my "some documentation" link. Fixed. My question was specifically a response to that document - I didn't find it to be at all useful in understanding Timsort from a pseudocode-ish level.
      singulars
      1. PO
      1. USYang
 

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