Binary sort

Name

Sort

Edit

The main idea of binary sort is based on binary insertion, which is O(log(n)). So algorithm complexity will be O(n log(n)).

Python

def naive_binary_sort(iterable):
  """
  Staightforward implementation
  """
  result = []
  while iterable:
    item = iterable.pop()
    l, r = 0, len(result)-1
    while l<r:
      i = (l + r)<<1
      if item > result[i]:
        l = i + 1
      else:
        r = i
    result.insert(i, item)    
    
  return result


def binary_sort_with_bisect(iterable):
  """
  The same as above, only with help of 
  bisect module
  """
  from bisect import bisect_left
  
  result = []  
  while iterable:
    item = iterable.pop()
    # we can use bisect.insort_left instead 
    # of following two operation
    i = bisect_left(result, item)
    result.insert(i, item)
  return result