Bisect, is it possible to work with descending sorted lists?

Question

How can I use bisect module on lists that are sorted descending? e.g.

import bisect  x = [1.0,2.0,3.0,4.0] # normal, ascending bisect.insort(x,2.5)  # -->  x is [1.0, 2.0, 2.5, 3.0, 4.0]     ok, works fine for ascending list  # however x = [1.0,2.0,3.0,4.0] x.reverse()           # -->  x is [4.0, 3.0, 2.0, 1.0]          descending list bisect.insort(x,2.5)  # -->  x is [4.0, 3.0, 2.0, 1.0, 2.5]     2.5 at end, not what I want really    

The only methods are insort (insort_right) or insort_left - none of which work for me.

Answer 1

Probably the easiest thing is to borrow the code from the library and make your own version

def reverse_insort(a, x, lo=0, hi=None):     """Insert item x in list a, and keep it reverse-sorted assuming a     is reverse-sorted.      If x is already in a, insert it to the right of the rightmost x.      Optional args lo (default 0) and hi (default len(a)) bound the     slice of a to be searched.     """     if lo < 0:         raise ValueError('lo must be non-negative')     if hi is None:         hi = len(a)     while lo < hi:         mid = (lo+hi)//2         if x > a[mid]: hi = mid         else: lo = mid+1     a.insert(lo, x) 

Answer 2

It is better to stick to the built-in python library, per @reve_etrange's comment unless you are working on a platform that allows you to use alternative C-extension implementations which might be faster. The following would leverage the built-in Python bisect module.

ASC = 'asc' DESC = 'desc'  def bisect_left(l, e, lo=None, hi=None, order=ASC):     """Find first index, starting from left, to insert e."""     lo = lo or 0     hi = hi or len(l)     if order not in (ASC, DESC):         raise ValueError('order must either be asc or desc.')     if order == ASC:         return bisect.bisect_left(l, e, lo, hi)     return len(l) - bisect.bisect_right(l[::-1], e, lo, hi)   def bisect_right(l, e, lo=None, hi=None, order=ASC):     """Find first index, starting from right, to insert e."""     lo = lo or 0     hi = hi or len(l)     if order not in (ASC, DESC):         raise ValueError('order must either be asc or desc.')     if order == ASC:         return bisect.bisect_right(l, e, lo, hi)     return len(l) - bisect.bisect_left(l[::-1], e, lo, hi)