I have devised a novel sorting algorithm, named Oracle Sort, which I believe is far superior to all currently known sorting algorithms (under certain assumptions). It utilizes an oracle to achieve a constant time complexity with regard to both the length of the input sequence and the number of distinct elements in the input sequence.
However, it seems that current computing is not yet ready for such an advanced algorithm, and therefore certain compromises had to be made and the algorithm had to be altered. As a result of these alterations, the performance of the provided algorithm has been much degraded. Therefore, I ask for any advice regarding the improvement of the time complexity of the algorithm as it stands.
Given below is an example implementation of the algorithm in Python 3.
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 == input_lst[min_idx] and \ candidate_lst[1:] == list(oraclesort(input_lst_without_min))