Timsort在降序数据上表现如何？

Question

来自于:

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

和:

http://en.wikipedia.org/wiki/Timsort

我看到Timsort在a0>a1>a2>... 的情况下有一些优化，但是对于下一个数组呢：

10000,10000,9999,9999,9998,9998,....,9,9,8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,1,0,0

这种数组的时间效率是多少？

（为了简单起见，使用整数。需要稳定排序）我已经做过一些测量，并且似乎这样的数组不是Timsort的“好”情况。

实际上，JDK中的TimSorthttp://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java 有一个方法“countRunAndMakeAscending”

@SuppressWarnings("unchecked")
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
    assert lo < hi;
    int runHi = lo + 1;
    if (runHi == hi)
        return 1;

    // Find end of run, and reverse range if descending
    if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
        while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
            runHi++;
        reverseRange(a, lo, runHi);
    } else {                              // Ascending
        while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
            runHi++;
    }

    return runHi - lo;
}

为什么不用另一种方式来实现它：

private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
    int runHi = lo;
    int lastEqual = lo;
    int ascending = 0;
    while (++runHi < hi) {
      int c = ((Comparable) a[runHi+1]).compareTo(a[runHi]);
      if (ascending == 0) {
        if (c != 0) {
          if (c > 0) {
            ascending = 1;
          } else {
            ascending = -1;
            reverseRange(a, lastEqual, runHi);
            lastEqual = runHi;
          }
        }
      } else if (ascending == 1) {
        if (c < 0) {
          return runHi - lo;
        }
      } else {
        if (c > 0) {
          reverseRange(a, lastEqual, runHi);
          reverseRange(a, lo, runHi);
          return runHi - lo;
        } else if (c < 0) {
          reverseRange(a, lastEqual, runHi);
          lastEqual = runHi;
        }
      }
    }
    if (ascending == -1) {
      reverseRange(a, lastEqual, runHi);
      reverseRange(a, lo, runHi);
    }
    return runHi - lo;
}

那么它可以在非升序的情况下正常工作吗？

- 4esn0k

Answer 1

是的。

基本上，它决定“升序”实际上意味着“非降序”，没有任何一般性损失 - 如果您有例如[5,5,4 3]，它将在下一次调用时将其分成[5,5]（升序）和[4,3]（降序）。

至于为什么，我想这是为了简单起见：只需尝试计算代码中 reverseRange() 的调用次数以及原始代码中的调用次数，您就会明白（我通过注意到理解一个版本需要多长时间，与另一个版本相比 :)）

编辑：WRONG WRONG WRONG！正如Oscar Smith指出的那样，原因是使timsort成为一种稳定的排序算法。如果有人知道如何转移不应得的赏金...

- loreb

---

我非常确定你给出的原因实际上是错误的。实际原因是为了确保排序是稳定的（相等的元素按照它们被给定的顺序返回）。如果您想按第一个元素对元组进行排序，这将非常有用。如果您有[(1,2),(2,0),(1,3)]，如果排序结果是[(1,3),(1,2),(2,0)]，那将是不好的。 - Oscar Smith

当我有大量空闲时间时，我计划做的事情之一是看看通过实现非稳定的timsort可以获得多大的性能提升。在某些情况下，我预计会有几个百分点的提高（在一些非常糟糕的情况下，可能是O(n) vs O(nlog(n))）。 - Oscar Smith