On the Worst-Case Complexity of TimSort

Re:On the Worst-Case Complexity of TimSort by toxik on Friday August 31, 2018 @08:53AM (#17885115)

The equivalent Python code works fine, though.

    >>> a=[0]*sum(rls)
    >>> sum=-1
    >>> for i in rls:
    ...   sum += i
    ...   a[sum] = 1
    ... 
    >>> a.sort()
    >>>

Takes a real good while, too.

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by iCannotEven on Friday August 31, 2018 @11:08AM (#17886171)

That's because the array to be sorted is packed and inflated, so as to be the worst possible input for that kind of sort.

Worst-case complexity.

Also, I needed to bump my JVM heap up to 16GB (not 9GB as recommended), just to run it.

[ Parent | on HN ]