Message11244

Author jeff.allen
Recipients jamesmudd, jeff.allen, stefan.richthofer, zyasoft
Date 2017-03-19.10:49:30
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1489920571.41.0.566221907432.issue2399@psf.upfronthosting.co.za>
In-reply-to
Content
A little more investigation shows that (for arrays that are not small, and in some circumstances) TimSort makes use of an auxilliary array that it will copy back into the main array in a merge-sort, doing comparisons along the way.

In Java, if one of those comparisons blows up part-way through a merge, the stack unwinds from there, and the copy that might have occurred is omitted:
http://hg.openjdk.java.net/jdk8u/jdk8u60/jdk/file/935758609767/src/share/classes/java/util/TimSort.java#l782

In CPython, when an exception is raised, the sorting is abandoned, but the merge function keeps its promise to put the elements back into the main array, here:
https://hg.python.org/cpython/file/v2.7.12/Objects/listobject.c#l1574

I can't find where either language promises not to mess up your list in these circumstances, so arguably test_sort is asking too much. But we like to do the same as CPython if we can. I don't like the obvious answer: preserve and restore the original list, doing more than CPython at considerable cost in memory. I think it follows logically that we would have to conceal the exception raised in the comparator, to let the Java sort run to completion somehow, then rethrow it.
History
Date User Action Args
2017-03-19 10:49:31jeff.allensetmessageid: <1489920571.41.0.566221907432.issue2399@psf.upfronthosting.co.za>
2017-03-19 10:49:31jeff.allensetrecipients: + jeff.allen, zyasoft, stefan.richthofer, jamesmudd
2017-03-19 10:49:31jeff.allenlinkissue2399 messages
2017-03-19 10:49:30jeff.allencreate