https://github.com/python/cpython/commit/24e5ad4689de9adc8e4a7d8c08fe400dcea... commit: 24e5ad4689de9adc8e4a7d8c08fe400dcea668e6 branch: master author: Stefan Pochmann <stefan.pochmann@gmail.com> committer: GitHub <noreply@github.com> date: 2020-02-03T08:47:20-08:00 summary: Fixes in sorting descriptions (GH-18317) Improvements in listsort.txt and a comment in sortperf.py. Automerge-Triggered-By: @csabella files: M Lib/test/sortperf.py M Objects/listsort.txt diff --git a/Lib/test/sortperf.py b/Lib/test/sortperf.py index 171e5cef5e29f..14a9d827ed57c 100644 --- a/Lib/test/sortperf.py +++ b/Lib/test/sortperf.py @@ -134,7 +134,7 @@ def tabulate(r): L = list(range(half - 1, -1, -1)) L.extend(range(half)) # Force to float, so that the timings are comparable. This is - # significantly faster if we leave tham as ints. + # significantly faster if we leave them as ints. L = list(map(float, L)) doit(L) # !sort print() diff --git a/Objects/listsort.txt b/Objects/listsort.txt index 43fe1574c3239..174777a2658dc 100644 --- a/Objects/listsort.txt +++ b/Objects/listsort.txt @@ -319,13 +319,13 @@ So merging is always done on two consecutive runs at a time, and in-place, although this may require some temp memory (more on that later). When a run is identified, its base address and length are pushed on a stack -in the MergeState struct. merge_collapse() is then called to see whether it -should merge it with preceding run(s). We would like to delay merging as -long as possible in order to exploit patterns that may come up later, but we -like even more to do merging as soon as possible to exploit that the run just -found is still high in the memory hierarchy. We also can't delay merging -"too long" because it consumes memory to remember the runs that are still -unmerged, and the stack has a fixed size. +in the MergeState struct. merge_collapse() is then called to potentially +merge runs on that stack. We would like to delay merging as long as possible +in order to exploit patterns that may come up later, but we like even more to +do merging as soon as possible to exploit that the run just found is still +high in the memory hierarchy. We also can't delay merging "too long" because +it consumes memory to remember the runs that are still unmerged, and the +stack has a fixed size. What turned out to be a good compromise maintains two invariants on the stack entries, where A, B and C are the lengths of the three rightmost not-yet @@ -739,7 +739,7 @@ slice (leaving off both endpoints) (2**(k-1)-1)+1 through (2**k-1)-1 inclusive = 2**(k-1) through (2**k-1)-1 inclusive, which has (2**k-1)-1 - 2**(k-1) + 1 = 2**k-1 - 2**(k-1) = - 2*2**k-1 - 2**(k-1) = + 2*2**(k-1)-1 - 2**(k-1) = (2-1)*2**(k-1) - 1 = 2**(k-1) - 1 elements.