Question: I need to append values to an existing list one by one, while maintaining the following two conditions at all times:  Every value in the list is unique  The list is always sorted in ascending order   The values are all integers, and there is a huge amount of them (literally millions, no exaggeration), and the list is dynamically constructed, values are added or removed depending on a changing condition, and I really need a very efficient way to do this. sorted(set(lst)) doesn't qualify as a solution because first the list is not pre-existing and I need to mutate it after that, the solution isn't efficient by itself and to maintain the two above conditions I need to repeat the inefficient method after every mutation, which is impractical to do and would take an unimaginable amount of time to process millions of numbers. One way to do it is to maintain a set with the same elements as the list, and do membership checking using the set and only add elements to the list if there aren't in the set, and add the same elements to both at the same time. This maintains uniqueness. To maintain the order use binary search to calculate the insertion index required and insert the element at the index. Example implementation I come up with without much thought: from bisect import bisect class Sorting_List: def __init__(self): self.data = [] self.unique = set() def add(self, n): if n in self.unique: return self.unique.add(n) if not self.data: self.data.append(n) return if n > self.data[-1]: self.data.append(n) elif n < self.data[0]: self.data.insert(0, n) elif len(self.data) == 2: self.data.insert(1, n) else: self.data.insert(bisect(self.data, n), n)  I am not satisfied with this solution, because I have to maintain a set, this isn't memory efficient and I don't think this is the most time efficient solution. I have done some tests: from timeit import timeit def test(n): setup = f'''from bisect import bisect from random import choice c = choice(range({n//2}, {n})) numbers = list(range({n}))''' linear = timeit('c in numbers', setup) / 1e6 binary = timeit('bisect(numbers, c) - 1 == c ', setup) / 1e6 return linear, binary  In [182]: [test(i) for i in range(1, 24)] Out[182]: [(3.1215199967846275e-08, 9.411800000816583e-08), (4.0730200009420514e-08, 9.4089699909091e-08), (5.392530001699925e-08, 1.0571250005159527e-07), (5.4071999969892203e-08, 1.111615999834612e-07), (5.495569994673133e-08, 1.3055420003365725e-07), (7.999380002729595e-08, 1.2215890001971274e-07), (6.739119999110698e-08, 1.1633279989473522e-07), (1.1775600002147258e-07, 1.2142769992351532e-07), (9.138470003381372e-08, 1.1602859990671277e-07), (1.212503999704495e-07, 1.2919300002977253e-07), (1.4093979995232076e-07, 1.1543070001062005e-07), (1.3911779993213713e-07, 1.1900339997373521e-07), (1.641304000513628e-07, 1.2721199996303767e-07), (2.2550319996662438e-07, 1.3572790008038284e-07), (2.0048839994706214e-07, 1.2690539995674044e-07), (2.0169020001776515e-07, 1.3345349999144673e-07), (1.482249000109732e-07, 1.2819399998988957e-07), (1.777580000925809e-07, 1.2856919993646443e-07), (1.5940839995164425e-07, 1.2710969999898224e-07), (2.772621000185609e-07, 1.4048079994972795e-07), (2.014727999921888e-07, 1.4225799997802823e-07), (2.851358000189066e-07, 1.3718699989840387e-07), (2.607858000556007e-07, 1.4413580007385463e-07)]  So the membership checking of lists is done using a linear search, by iterating through the list one by one and perform equality checking, this is inefficient but beats binary search for small number of elements (n <= 12) and is much slower for larger amounts. In [183]: test(256) Out[183]: (2.5505281999940053e-06, 1.7594210000243037e-07)  And set membership checking is faster than binary search, which is much faster than linear search: In [188]: lst = list(range(256)) In [189]: s = set(lst) In [190]: %timeit 199 in s 42.5 ns ± 0.946 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each) In [191]: %timeit bisect(lst, 199) 159 ns ± 1.38 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each) In [192]: %timeit 199 in lst 2.53 µs ± 31.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)  How can we devise a faster method?  I am well aware that Python sets are unordered, and sorting sets yields lists. But perhaps there are some external libraries that provide ordered sets, if there are then I am not aware of them and I haven't used them. Solutions using such ordered sets are welcome so long as they are performant, but I am not asking for recommendations so please don't close the question for that reason. Nevertheless ordered sets only fulfill the first criterium, only uniqueness is maintained, and I need the orderedness to be maintained as well. list here is just terminology, in plain Python list is the only ordered mutable sequence. Other data types are welcome. About SQLite, I haven't tested in-memory transient databases yet, but for a local HDD based database, the I/O delay is many milliseconds which is unacceptable.  I have just performed yet another test: In [243]: numbers = random.choices(range(4294967295), k=1048576) In [244]: sl = Sorting_List() In [245]: ss = SortedSet() In [246]: %timeit for i in numbers: ss.add(i) 306 ms ± 8.55 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [247]: %timeit for i in numbers: sl.add(i) --------------------------------------------------------------------------- KeyboardInterrupt Traceback (most recent call last) ... In [248]: sls = SortedList() In [249]: s = set() In [250]: %%timeit ...: for i in numbers: ...: if i not in s: ...: sls.add(i) ...: s.add(i) 145 ms ± 3.24 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [251]: len(numbers) Out[251]: 1048576  It seems my custom implementation is at least as performant as SortedSet for reasonable amount of data, I need much more efficient methods. For a million elements my method becomes very inefficient indeed, while SortedSet and SortedList both keep being competent. And now it seems a SortedList plus a set for membership checking is the most time efficient method, but obviously not very memory efficient, just as my custom implementation. But my custom implementation seems to outperform SortedSet which seems to be memory efficient.  Testing SortedList by adding 2^20 elements one by one, while keeping the elements unique by doing membership checking using the container itself: In [252]: sls = SortedList() In [253]: %%timeit ...: for i in numbers: ...: if i not in sls: ...: sls.add(i) 1.93 s ± 16.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)  (numbers is defined above) The test clearly shows SortedList membership checking is slow, as suspected, it uses linear search.

Answer: I like data rather than guessing so I profiled the approaches suggested by @Kelly Bundy from bisect import bisect from sortedcontainers import SortedList, SortedSet class Sorting_List: # The Original def __init__(self): self.data = [] self.unique = set() def add(self, n): if n in self.unique: return self.unique.add(n) if not self.data: self.data.append(n) return if n > self.data[-1]: self.data.append(n) elif n < self.data[0]: self.data.insert(0, n) elif len(self.data) == 2: self.data.insert(1, n) else: self.data.insert(bisect(self.data, n), n) class Sorting_List_Kelly: def __init__(self): self.data = [] self.unique = set() def add(self, n): if n in self.unique: return self.unique.add(n) self.data[bisect(self.data, n) : 0] = (n,) class SortedListWrapper: def __init__(self): self.data = SortedList() self.unique = set() def add(self, n): if n in self.unique: return self.unique.add(n) self.data.add(n)  import random from performance_measurement import run_performance_comparison def original(values): x = Sorting_List() for value in values: x.add(value) return x.data def kelly(values): x = Sorting_List_Kelly() for value in values: x.add(value) return x.data def sortedset(values): x = SortedSet() for value in values: x.add(value) return x def sortedlist(values): x = SortedListWrapper() for value in values: x.add(value) return x def generate_lists(N): return [random.sample(range(N), N)] data_size = [1000, 2000, 3000, 4000, 5000, 10000, 20000, 30000, 40000, 50000] approaches = [original, kelly, sortedset, sortedlist] run_performance_comparison(approaches, data_size, setup=generate_lists)   Especially for small problem instances @Kelly Bundy's improved approach outperforms SortedList with a wrapper and SortedSet from sortedcontainers.  Profiling code: import timeit import matplotlib.pyplot as plt from typing import List, Dict, Callable from contextlib import contextmanager @contextmanager def data_provider(data_size, setup=lambda N: N, teardown=lambda: None): data = setup(data_size) yield data teardown() def run_performance_comparison(approaches: List[Callable], data_size: List[int], setup=lambda N: N, teardown=lambda: None, number_of_repetitions=5, title='N'): approach_times: Dict[Callable, List[float]] = {approach: [] for approach in approaches} for N in data_size: with data_provider(N, setup, teardown) as data: for approach in approaches: approach_time = timeit.timeit(lambda: approach(*data), number=number_of_repetitions) approach_times[approach].append(approach_time) for approach in approaches: plt.plot(data_size, approach_times[approach], label=approach.__name__) plt.xlabel(title) plt.ylabel('Execution Time (seconds)') plt.title('Performance Comparison') plt.legend() plt.show()