Sorting Algorithms Mastery

Sorting Algorithms Mastery

Before a generative model can help you discover a drug, its output must be organized. A GAN, VAE, or diffusion model trained on molecular structures can produce tens of thousands of candidate molecules in a single sampling run, but raw generation is unordered by nature. To turn that output into a shortlist for synthesis, we rely on sorting: ranking candidates by predicted binding affinity, drug-likeness (QED score), or synthetic accessibility. Sorting is also central to data preparation, where training sets are ordered for reproducible batching, and to evaluation, where metrics such as top-k precision require candidates to be ranked before selection. Formally, a sorting algorithm rearranges a collection of items so that they follow a defined order, typically numeric or lexicographic. The efficiency of a sorting algorithm is described by its time complexity, expressed in Big-O notation. Naive comparison-based sorts such as bubble sort and insertion sort run in O(n²) time, meaning the work grows quadratically with the number of items. Divide-and-conquer algorithms such as merge sort and quicksort achieve O(n log n) on average, which is effectively optimal for comparison-based sorting. When you are ranking 100,000 generated molecules, the difference between these complexity classes is the difference between seconds and hours of computation. Two properties matter most when choosing an algorithm for a scientific pipeline. First, stability : a stable sort preserves the original relative order of items with equal keys. This matters when you sort molecules by docking score and want ties broken by the order in which the model generated them. Second, adaptivity : some algorithms exploit partially ordered data to run faster. Python's built-in sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort that is stable, adaptive, and highly optimized in C, making it the right default choice in practice. The example below implements merge sort from scratch to rank molecules produced by a generative model. Each candidate is a dictionary containing a SMILES string and a predicted docking score, where lower (more negative) scores indicate stronger predicted binding. Merge sort recursively splits the list in half, sorts each half, and merges the sorted halves, guaranteeing O(n log n) time in all cases. def merge_sort(candidates): """Sort generated molecules by docking score (ascending).""" if len(candidates) <= 1: return candidates mid = len(candidates) // 2 left = merge_sort(candidates[:mid]) right = merge_sort(candidates[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i]["docking_score"] <= right[j]["docking_score"]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result # Candidates sampled from a diffusion model samples = [ {"smiles": "CC(=O)Oc1ccccc1C(=O)O", "docking_score": -8.4}, {"smiles": "c1ccccc1O", "docking_score": -6.2}, {"smiles": "CN1C=NC2=C1C(=O)N(C)C(=O)N2C", "docking_score": -7.9}, ] for mol in merge_sort(samples): print(mol["smiles"], mol["docking_score"]) In production code, you would almost always use Python's built-in Timsort instead of hand-rolling an algorithm. The built-in version is stable, battle-tested, and supports a key function for sorting on computed values or multiple criteria at once. The next example performs a two-stage ranking of generative output: primary sort by docking score (most negative first) and secondary sort by QED drug-likeness (highest first) for candidates with comparable affinity. Note the negation trick, -m["qed"] , which flips a descending criterion into an ascending one so a single ascending sort handles both. candidates = [ {"smiles": "CC(=O)Oc1ccccc1C(=O)O", "docking_score": -8.4, "qed": 0.72}, {"smiles": "CN1C=NC2=C1C(=O)N(C)C(=O)N2C", "docking_score": -7.9, "qed": 0.85}, {"smiles": "c1ccccc1O", "docking_score": -6.2, "qed": 0.91}, ] # Rank: strongest predicted binding first; break ties by higher QED ranked = sorted( candidates, key=lambda m: (m["docking_score"], -m["qed"]), ) for rank, mol in enumerate(ranked, start=1): print(f"{rank}. {mol['smiles']} | score={mol['docking_score']} | QED={mol['qed']}") # Top-k selection: keep the 2 most promising molecules for synthesis shortlist = ranked[:2] Understanding sorting also sharpens your intuition about model evaluation. When a paper reports that a generative model placed a known active compound in its "top 1% of ranked candidates," that claim depends entirely on a sort: the model's scores were ordered, and the active compound's position was measured against that ordering. If the sort is unstable, or if the key function is mis-specified, the reported ranking, and the scientific conclusion drawn from it, can silently change. As a computational scientist, you should be able to read a ranking pipeline and verify both the algorithm and the key. Sorting converts unordered generative output (GAN samples, VAE decodings, diffusion samples) into ranked candidate lists for drug discovery workflows. Comparison-based sorts cannot beat O(n log n) in the general case; O(n²) sorts like bubble sort are impractical for large molecular libraries. Merge sort guarantees O(n log n) and is stable; quicksort is faster in practice on average but has an O(n²) worst case. Stability preserves the original order of tied items, which matters for reproducible, auditable rankings of model output. Python's built-in sorted() uses Timsort (stable, adaptive) and supports multi-criteria ranking through a key function; prefer it over custom implementations. Top-k selection, percentile reporting, and "hit rate" metrics all depend on a correct, well-specified sort of model scores. Practice exercise: Generate (or write out by hand) a list of ten synthetic candidate molecules, each with a SMILES string, a docking score between −12.0 and −4.0, and a QED score between 0 and 1. First, implement quicksort yourself to rank these candidates by docking score, and state its average and worst-case time complexities. Then re-rank the same list using Python's built-in sorted() with a key that sorts by docking score ascending and QED descending, and verify that both approaches produce the same primary ordering. Finally, time both implementations on a list of 10,000