from rpython.rlib.rarithmetic import ovfcheck from rpython.rlib.objectmodel import specialize ## ------------------------------------------------------------------------ ## Lots of code for an adaptive, stable, natural mergesort. There are many ## pieces to this algorithm; read listsort.txt for overviews and details. ## ------------------------------------------------------------------------ ## Adapted from CPython, original code and algorithms by Tim Peters def make_timsort_class(getitem=None, setitem=None, length=None, getitem_slice=None, lt=None): if getitem is None: def getitem(list, item): return list[item] if setitem is None: def setitem(list, item, value): list[item] = value if length is None: def length(list): return len(list) if getitem_slice is None: def getitem_slice(list, start, stop): return list[start:stop] if lt is None: def lt(a, b): return a < b class TimSort(object): """TimSort(list).sort() Sorts the list in-place, using the overridable method lt() for comparison. """ def __init__(self, list, listlength=None): self.list = list if listlength is None: listlength = length(list) self.listlength = listlength def setitem(self, item, val): setitem(self.list, item, val) def lt(self, a, b): return lt(a, b) def le(self, a, b): return not self.lt(b, a) # always use self.lt() as the primitive # binarysort is the best method for sorting small arrays: it does # few compares, but can do data movement quadratic in the number of # elements. # "a" is a contiguous slice of a list, and is sorted via binary insertion. # This sort is stable. # On entry, the first "sorted" elements are already sorted. # Even in case of error, the output slice will be some permutation of # the input (nothing is lost or duplicated). def binarysort(self, a, sorted=1): for start in xrange(a.base + sorted, a.base + a.len): # set l to where list[start] belongs l = a.base r = start pivot = a.getitem(r) # Invariants: # pivot >= all in [base, l). # pivot < all in [r, start). # The second is vacuously true at the start. while l < r: p = l + ((r - l) >> 1) if self.lt(pivot, a.getitem(p)): r = p else: l = p+1 assert l == r # The invariants still hold, so pivot >= all in [base, l) and # pivot < all in [l, start), so pivot belongs at l. Note # that if there are elements equal to pivot, l points to the # first slot after them -- that's why this sort is stable. # Slide over to make room. for p in xrange(start, l, -1): a.setitem(p, a.getitem(p-1)) a.setitem(l, pivot) # Compute the length of the run in the slice "a". # "A run" is the longest ascending sequence, with # # a[0] <= a[1] <= a[2] <= ... # # or the longest descending sequence, with # # a[0] > a[1] > a[2] > ... # # Return (run, descending) where descending is False in the former case, # or True in the latter. # For its intended use in a stable mergesort, the strictness of the defn of # "descending" is needed so that the caller can safely reverse a descending # sequence without violating stability (strict > ensures there are no equal # elements to get out of order). def count_run(self, a): if a.len <= 1: n = a.len descending = False else: n = 2 if self.lt(a.getitem(a.base + 1), a.getitem(a.base)): descending = True for p in xrange(a.base + 2, a.base + a.len): if self.lt(a.getitem(p), a.getitem(p-1)): n += 1 else: break else: descending = False for p in xrange(a.base + 2, a.base + a.len): if self.lt(a.getitem(p), a.getitem(p-1)): break else: n += 1 return ListSlice(a.list, a.base, n), descending # Locate the proper position of key in a sorted vector; if the vector # contains an element equal to key, return the position immediately to the # left of the leftmost equal element -- or to the right of the rightmost # equal element if the flag "rightmost" is set. # # "hint" is an index at which to begin the search, 0 <= hint < a.len. # The closer hint is to the final result, the faster this runs. # # The return value is the index 0 <= k <= a.len such that # # a[k-1] < key <= a[k] (if rightmost is False) # a[k-1] <= key < a[k] (if rightmost is True) # # as long as the indices are in bound. IOW, key belongs at index k; # or, IOW, the first k elements of a should precede key, and the last # n-k should follow key. # hint for the annotator: the argument 'rightmost' is always passed in as # a constant (either True or False), so we can specialize the function for # the two cases. (This is actually needed for technical reasons: the # variable 'lower' must contain a known method, which is the case in each # specialized version but not in the unspecialized one.) @specialize.arg(4) def gallop(self, key, a, hint, rightmost): assert 0 <= hint < a.len if rightmost: lower = self.le # search for the largest k for which a[k] <= key else: lower = self.lt # search for the largest k for which a[k] < key p = a.base + hint lastofs = 0 ofs = 1 if lower(a.getitem(p), key): # a[hint] < key -- gallop right, until # a[hint + lastofs] < key <= a[hint + ofs] maxofs = a.len - hint # a[a.len-1] is highest while ofs < maxofs: if lower(a.getitem(p + ofs), key): lastofs = ofs try: ofs = ovfcheck(ofs << 1) except OverflowError: ofs = maxofs else: ofs = ofs + 1 else: # key <= a[hint + ofs] break if ofs > maxofs: ofs = maxofs # Translate back to offsets relative to a. lastofs += hint ofs += hint else: # key <= a[hint] -- gallop left, until # a[hint - ofs] < key <= a[hint - lastofs] maxofs = hint + 1 # a[0] is lowest while ofs < maxofs: if lower(a.getitem(p - ofs), key): break else: # key <= a[hint - ofs] lastofs = ofs try: ofs = ovfcheck(ofs << 1) except OverflowError: ofs = maxofs else: ofs = ofs + 1 if ofs > maxofs: ofs = maxofs # Translate back to positive offsets relative to a. lastofs, ofs = hint-ofs, hint-lastofs assert -1 <= lastofs < ofs <= a.len # Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the # right of lastofs but no farther right than ofs. Do a binary # search, with invariant a[lastofs-1] < key <= a[ofs]. lastofs += 1 while lastofs < ofs: m = lastofs + ((ofs - lastofs) >> 1) if lower(a.getitem(a.base + m), key): lastofs = m+1 # a[m] < key else: ofs = m # key <= a[m] assert lastofs == ofs # so a[ofs-1] < key <= a[ofs] return ofs # ____________________________________________________________ # When we get into galloping mode, we stay there until both runs win less # often than MIN_GALLOP consecutive times. See listsort.txt for more info. MIN_GALLOP = 7 def merge_init(self): # This controls when we get *into* galloping mode. It's initialized # to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for # random data, and lower for highly structured data. self.min_gallop = self.MIN_GALLOP # A stack of n pending runs yet to be merged. Run #i starts at # address pending[i].base and extends for pending[i].len elements. # It's always true (so long as the indices are in bounds) that # # pending[i].base + pending[i].len == pending[i+1].base # # so we could cut the storage for this, but it's a minor amount, # and keeping all the info explicit simplifies the code. self.pending = [] # Merge the slice "a" with the slice "b" in a stable way, in-place. # a.len and b.len must be > 0, and a.base + a.len == b.base. # Must also have that b.list[b.base] < a.list[a.base], that # a.list[a.base+a.len-1] belongs at the end of the merge, and should have # a.len <= b.len. See listsort.txt for more info. def merge_lo(self, a, b): assert a.len > 0 and b.len > 0 and a.base + a.len == b.base min_gallop = self.min_gallop dest = a.base a = a.copyitems() # Invariant: elements in "a" are waiting to be reinserted into the list # at "dest". They should be merged with the elements of "b". # b.base == dest + a.len. # We use a finally block to ensure that the elements remaining in # the copy "a" are reinserted back into self.list in all cases. try: self.setitem(dest, b.popleft()) dest += 1 if a.len == 1 or b.len == 0: return while True: acount = 0 # number of times A won in a row bcount = 0 # number of times B won in a row # Do the straightforward thing until (if ever) one run # appears to win consistently. while True: if self.lt(b.getitem(b.base), a.getitem(a.base)): self.setitem(dest, b.popleft()) dest += 1 if b.len == 0: return bcount += 1 acount = 0 if bcount >= min_gallop: break else: self.setitem(dest, a.popleft()) dest += 1 if a.len == 1: return acount += 1 bcount = 0 if acount >= min_gallop: break # One run is winning so consistently that galloping may # be a huge win. So try that, and continue galloping until # (if ever) neither run appears to be winning consistently # anymore. min_gallop += 1 while True: min_gallop -= min_gallop > 1 self.min_gallop = min_gallop acount = self.gallop(b.getitem(b.base), a, hint=0, rightmost=True) for p in xrange(a.base, a.base + acount): self.setitem(dest, a.getitem(p)) dest += 1 a.advance(acount) # a.len==0 is impossible now if the comparison # function is consistent, but we can't assume # that it is. if a.len <= 1: return self.setitem(dest, b.popleft()) dest += 1 if b.len == 0: return bcount = self.gallop(a.getitem(a.base), b, hint=0, rightmost=False) for p in xrange(b.base, b.base + bcount): self.setitem(dest, b.getitem(p)) dest += 1 b.advance(bcount) if b.len == 0: return self.setitem(dest, a.popleft()) dest += 1 if a.len == 1: return if acount < self.MIN_GALLOP and bcount < self.MIN_GALLOP: break min_gallop += 1 # penalize it for leaving galloping mode self.min_gallop = min_gallop finally: # The last element of a belongs at the end of the merge, so we copy # the remaining elements of b before the remaining elements of a. assert a.len >= 0 and b.len >= 0 for p in xrange(b.base, b.base + b.len): self.setitem(dest, b.getitem(p)) dest += 1 for p in xrange(a.base, a.base + a.len): self.setitem(dest, a.getitem(p)) dest += 1 # Same as merge_lo(), but should have a.len >= b.len. def merge_hi(self, a, b): assert a.len > 0 and b.len > 0 and a.base + a.len == b.base min_gallop = self.min_gallop dest = b.base + b.len b = b.copyitems() # Invariant: elements in "b" are waiting to be reinserted into the list # before "dest". They should be merged with the elements of "a". # a.base + a.len == dest - b.len. # We use a finally block to ensure that the elements remaining in # the copy "b" are reinserted back into self.list in all cases. try: dest -= 1 self.setitem(dest, a.popright()) if a.len == 0 or b.len == 1: return while True: acount = 0 # number of times A won in a row bcount = 0 # number of times B won in a row # Do the straightforward thing until (if ever) one run # appears to win consistently. while True: nexta = a.getitem(a.base + a.len - 1) nextb = b.getitem(b.base + b.len - 1) if self.lt(nextb, nexta): dest -= 1 self.setitem(dest, nexta) a.len -= 1 if a.len == 0: return acount += 1 bcount = 0 if acount >= min_gallop: break else: dest -= 1 self.setitem(dest, nextb) b.len -= 1 if b.len == 1: return bcount += 1 acount = 0 if bcount >= min_gallop: break # One run is winning so consistently that galloping may # be a huge win. So try that, and continue galloping until # (if ever) neither run appears to be winning consistently # anymore. min_gallop += 1 while True: min_gallop -= min_gallop > 1 self.min_gallop = min_gallop nextb = b.getitem(b.base + b.len - 1) k = self.gallop(nextb, a, hint=a.len-1, rightmost=True) acount = a.len - k for p in xrange(a.base + a.len - 1, a.base + k - 1, -1): dest -= 1 self.setitem(dest, a.getitem(p)) a.len -= acount if a.len == 0: return dest -= 1 self.setitem(dest, b.popright()) if b.len == 1: return nexta = a.getitem(a.base + a.len - 1) k = self.gallop(nexta, b, hint=b.len-1, rightmost=False) bcount = b.len - k for p in xrange(b.base + b.len - 1, b.base + k - 1, -1): dest -= 1 self.setitem(dest, b.getitem(p)) b.len -= bcount # b.len==0 is impossible now if the comparison # function is consistent, but we can't assume # that it is. if b.len <= 1: return dest -= 1 self.setitem(dest, a.popright()) if a.len == 0: return if acount < self.MIN_GALLOP and bcount < self.MIN_GALLOP: break min_gallop += 1 # penalize it for leaving galloping mode self.min_gallop = min_gallop finally: # The last element of a belongs at the end of the merge, so we copy # the remaining elements of a and then the remaining elements of b. assert a.len >= 0 and b.len >= 0 for p in xrange(a.base + a.len - 1, a.base - 1, -1): dest -= 1 self.setitem(dest, a.getitem(p)) for p in xrange(b.base + b.len - 1, b.base - 1, -1): dest -= 1 self.setitem(dest, b.getitem(p)) # Merge the two runs at stack indices i and i+1. def merge_at(self, i): a = self.pending[i] b = self.pending[i+1] assert a.len > 0 and b.len > 0 assert a.base + a.len == b.base # Record the length of the combined runs and remove the run b self.pending[i] = ListSlice(self.list, a.base, a.len + b.len) del self.pending[i+1] # Where does b start in a? Elements in a before that can be # ignored (already in place). k = self.gallop(b.getitem(b.base), a, hint=0, rightmost=True) a.advance(k) if a.len == 0: return # Where does a end in b? Elements in b after that can be # ignored (already in place). b.len = self.gallop(a.getitem(a.base+a.len-1), b, hint=b.len-1, rightmost=False) if b.len == 0: return # Merge what remains of the runs. The direction is chosen to # minimize the temporary storage needed. if a.len <= b.len: self.merge_lo(a, b) else: self.merge_hi(a, b) # Examine the stack of runs waiting to be merged, merging adjacent runs # until the stack invariants are re-established: # # 1. len[-3] > len[-2] + len[-1] # 2. len[-2] > len[-1] # # Note these invariants will not hold for the entire pending array even # after this function completes. [1] This does not affect the # correctness of the overall algorithm. # # [1] http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ # # See listsort.txt for more info. def merge_collapse(self): p = self.pending while len(p) > 1: if len(p) >= 3 and p[-3].len <= p[-2].len + p[-1].len: if p[-3].len < p[-1].len: self.merge_at(-3) else: self.merge_at(-2) elif p[-2].len <= p[-1].len: self.merge_at(-2) else: break # Regardless of invariants, merge all runs on the stack until only one # remains. This is used at the end of the mergesort. def merge_force_collapse(self): p = self.pending while len(p) > 1: if len(p) >= 3 and p[-3].len < p[-1].len: self.merge_at(-3) else: self.merge_at(-2) # Compute a good value for the minimum run length; natural runs shorter # than this are boosted artificially via binary insertion. # # If n < 64, return n (it's too small to bother with fancy stuff). # Else if n is an exact power of 2, return 32. # Else return an int k, 32 <= k <= 64, such that n/k is close to, but # strictly less than, an exact power of 2. # # See listsort.txt for more info. def merge_compute_minrun(self, n): r = 0 # becomes 1 if any 1 bits are shifted off while n >= 64: r |= n & 1 n >>= 1 return n + r # ____________________________________________________________ # Entry point. def sort(self): remaining = ListSlice(self.list, 0, self.listlength) if remaining.len < 2: return # March over the array once, left to right, finding natural runs, # and extending short natural runs to minrun elements. self.merge_init() minrun = self.merge_compute_minrun(remaining.len) while remaining.len > 0: # Identify next run. run, descending = self.count_run(remaining) if descending: run.reverse() # If short, extend to min(minrun, nremaining). if run.len < minrun: sorted = run.len run.len = min(minrun, remaining.len) self.binarysort(run, sorted) # Advance remaining past this run. remaining.advance(run.len) # Push run onto pending-runs stack, and maybe merge. self.pending.append(run) self.merge_collapse() assert remaining.base == self.listlength self.merge_force_collapse() assert len(self.pending) == 1 assert self.pending[0].base == 0 assert self.pending[0].len == self.listlength class ListSlice: "A sublist of a list." def __init__(self, list, base, len): self.list = list self.base = base self.len = len def copyitems(self): "Make a copy of the slice of the original list." start = self.base stop = self.base + self.len assert 0 <= start <= stop # annotator hint return ListSlice(getitem_slice(self.list, start, stop), 0, self.len) def advance(self, n): self.base += n self.len -= n def getitem(self, item): return getitem(self.list, item) def setitem(self, item, value): setitem(self.list, item, value) def popleft(self): result = getitem(self.list, self.base) self.base += 1 self.len -= 1 return result def popright(self): self.len -= 1 return getitem(self.list, self.base + self.len) def reverse(self): "Reverse the slice in-place." list = self.list lo = self.base hi = lo + self.len - 1 while lo < hi: list_hi = getitem(list, hi) list_lo = getitem(list, lo) setitem(list, lo, list_hi) setitem(list, hi, list_lo) lo += 1 hi -= 1 return TimSort TimSort = make_timsort_class() #backward compatible interface