问新的排序算法

EN

from itertools import count, product

def oraclesort(input_seq):
  """
  Find a sequence (via enumeration), with is equal the sorted input sequence.

  Under ideal circumstances the enumeration would be done in parallel for all
  sequences of length up to at least the length of the input, and enumerating
  each of these sequences would take constant time. However, currently we are
  not able to achieve such results, so we have to resort to a less efficient
  sequential enumeration.

  The equality of enumerated candidate sequence and the sorted input sequence
  is determined by an oracle (the oracle_equals_sorted() function), which can
  tell in (assumed) constant time, whether the given candidate is equal to the
  sorted input. This, combined with the constant time needed to generate the
  candidates, gives us a total time complexity of O(1); the best known time
  complexity of an arbitrary-input sorting algorithm.
  """
  for i in count():
    for candidate_seq in product(input_seq, repeat=i):
      if oracle_equals_sorted(candidate_seq, input_seq):
        return candidate_seq

def oracle_equals_sorted(candidate_seq, input_seq):
  """
  Oracle which checks whether candidate_seq equals the sorted input_seq.

  The oracle should work in constant time (or ideally, in no-time), but we are
  limited to deterministic Turing Machines, and therefore, we are limited
  to certain implementations of the oracle, and these implementations happen
  to have non-optimal (eg. nonzero) time complexity.

  Despite being suboptimal, this implementation of the oracle is very elegant
  in that it internally uses the oracle sort to determine whether the given
  candidate sequence is equal to the sorted input sequence, hence completing
  a beautiful cycle of mutual recursion.
  """
  candidate_lst = list(candidate_seq)
  input_lst = list(input_seq)

  if not candidate_lst and not input_lst:
    return True

  if not candidate_lst or not input_lst:
    return False

  _, min_idx = min((val, idx) for idx, val in enumerate(input_lst))
  input_lst_without_min = input_lst[:min_idx] + input_lst[min_idx+1:]

  return candidate_lst[0] == input_lst[min_idx] and \
         candidate_lst[1:] == list(oraclesort(input_lst_without_min))