diff options
| author | Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> | 2020-02-03 16:50:29 -0800 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2020-02-03 16:50:29 -0800 |
| commit | a0389ba84bb2dbee7a59e25163e514059afc166d (patch) | |
| tree | 8c707cefa942cd79d902d8bfad65e093946bbb24 /Objects/listsort.txt | |
| parent | d01ae1b22330992eadc7b2a0842ead544f7e507d (diff) | |
| download | cpython-git-a0389ba84bb2dbee7a59e25163e514059afc166d.tar.gz | |
Fixes in sorting descriptions (GH-18317)
Improvements in listsort.txt and a comment in sortperf.py.
Automerge-Triggered-By: @csabella
(cherry picked from commit 24e5ad4689de9adc8e4a7d8c08fe400dcea668e6)
Co-authored-by: Stefan Pochmann <stefan.pochmann@gmail.com>
Diffstat (limited to 'Objects/listsort.txt')
| -rw-r--r-- | Objects/listsort.txt | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/Objects/listsort.txt b/Objects/listsort.txt index 43fe1574c3..174777a265 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. |