Cycle sort for minimal writes
Sorting is routine in programming, yet the cost model is not uniform. Comparing two integers in CPU memory is cheap; moving a value across persistent storage can involve wear levelling, checksums, or a costly log append. When assignments dominate, an algorithm that performs fewer writes can outperform a general-purpose sort even if it performs many more comparisons. Cycle sort is designed around that imbalance.
Cycle sort treats an array as a collection of permutation cycles. Instead of repeatedly shifting neighbouring values, it identifies where a misplaced item belongs, places it there directly, and keeps the displaced item in a temporary variable until its destination is known. In the clean case of distinct values, every cell that changes receives one write. The method is built for minimal writes and works best with small, bounded arrays.
This is not merely a laboratory concern. Firmware images, compact event journals, and EEPROM-backed records can have a limited endurance budget, while a nightly reconciliation process may repeatedly rewrite records on a server’s solid-state drive. Even in ordinary commerce, catalogue updates for an Australian electronics retailer such as JB Hi-Fi or Kogan can turn a seemingly simple ordering task into thousands of physical writes.
The trade-off is substantial: cycle sort generally performs (O(n^2)) comparisons, uses constant auxiliary space, and does not preserve the original order of equal keys. It suits bounded batches where write volume is the scarce resource, rather than large, nearly sorted collections that Python’s built-in sort handles efficiently. Its mechanics, correctness, and practical boundaries are best understood through permutation cycles.
When writes matter more than comparisons
Write-minimal behaviour matters because a swap or shift often touches more memory than the visible result suggests. An insertion sort may move a value through many positions, and a quicksort partition repeatedly exchanges pairs of records. Cycle sort instead asks one question for each displaced value: which final cell currently holds the item that belongs there? The answer forms a cycle, allowing one array assignment to place one value and expose the next displaced member of that cycle.
Compared with moving a full record containing keys, pointers, timestamps, and application metadata, the saving can be substantial. That does not make all writes identical: firmware media has different constraints from a database transaction log, and volatile RAM has almost none. The sorting complexity comparison is useful for separating asymptotic time from write behaviour, which many summaries combine into a single ranking.
Permutations, cycles, and destinations
Consider the distinct values [4, 2, 1, 3]. Their sorted destinations are indices 3, 1, 0, and 2, so position 1 is already fixed while positions 0, 3, and 2 form the cycle 0 → 3 → 2 → 0. The cycle sort operation holds 4, writes it to index 3, then holds the displaced 3 and writes it to index 2. Finally, 1 goes to index 0, leaving the array as [1, 2, 3, 4].
Only three array cells change, and the procedure performs three array writes. The value held at the end is already present in a cell written earlier, so writing it again would violate the minimal-write goal. In this direct-placement model, an unchanged cell needs no assignment, while each changed cell needs at least one; cycle sort reaches that lower bound.
Duplicates require a precise definition of the final position. Two equal keys may be interchangeable, or they may have distinct destinations determined by their old indices. The implementation below assumes distinct comparable values. A production version can preserve stability by treating each key and original position as a unique pair, though that adds bookkeeping and may require extra storage for the original indices.
A direct-placement implementation
The algorithm processes a growing sorted prefix. For each starting index, it counts how many remaining values are smaller than the current item. That count gives the item’s destination relative to the suffix. If the item is already there, it is skipped; otherwise, the current destination is overwritten with the held item, and the displaced value becomes the next item whose destination must be found.
def cycle_sort(values):
n = len(values)
writes = 0
def destination(item, start):
target = start
for index in range(start + 1, n):
if values[index] < item:
target += 1
return target
for start in range(n - 1):
item = values[start]
target = destination(item, start)
if target == start:
continue
while values[target] != item:
displaced = values[target]
values[target] = item
writes += 1
item = displaced
target = destination(item, start)
return writes
The inner loop closes when the held value is found at its destination, rather than forcing another assignment. For [4, 2, 1, 3], the function reports three writes. The counter records assignments to array cells, not comparisons or local-variable operations. Scan work is quadratic, but the number of assignments is linear and, more tightly, proportional to the number of cells whose contents change.
A bounded batch is essential. A continuous feed does not have a natural final index, and sorting every arriving event would be wasteful. Systems with a steady producer-consumer flow can borrow the buffering pattern described in this Python ring buffer guide: collect a finite window, order it once, then release the ordered batch while new data continues to arrive.
Correctness, duplicates, and edge cases
Correctness follows from an invariant: before an outer iteration, the prefix before start is sorted and contains that prefix’s smallest values. The suffix consequently retains every larger value exactly once. Counting smaller suffix values locates the held item in the fully sorted order. Each overwrite places that item correctly and removes it from the unresolved set, so repeating the step eventually resolves the whole permutation cycle.
Empty and single-element inputs need no work, while an already sorted array causes zero writes. Reverse order may place every cell in a different position, producing the maximum linear number of writes. Non-numeric objects need a consistent comparison rule. Equal keys are the main caveat: without unique destinations, the closure test may confuse equal occurrences. Adding original indices as tie-breakers resolves the ambiguity but makes stability an explicit requirement rather than an incidental property.
Practical workloads and Australian settings
Write-sensitive uses include microcontroller flash, EEPROM, wearable logs, and archival files where each replacement consumes space or endurance. A practical batch can also arise during an ordinary Australian grocery run: a supermarket such as Woolworths or Coles may sort shelf labels, temporary price boards, or stock tasks by expiry and priority. The shopper sees a simple store, while the back-office system may update many records with little benefit from extra comparisons.
Transport data offers another example. An operator reconciling Melbourne myki tap events or Sydney public transport feeds may process bounded daily batches, assign urgency levels, and write only changed operational records. Cycle sort cannot decide which event matters, but once priorities are assigned, it can order them with a small write count. Under the Australian Consumer Law, price representations must not be misleading; a correct sort does not validate the source data.
Analytics pipelines often combine grouping with ordering. Customer segmentation may use Gaussian mixture clustering to create cohorts, after which cycle sort can place records within each cohort according to a priority score. This division of labour is sensible: the clustering stage estimates structure, while direct placement handles the final permutation without repeatedly rewriting a growing array.
Choosing between sorting strategies
No sorting method wins every workload. Insertion sort is stable, simple, and efficient on tiny or nearly sorted arrays. Merge sort and Python’s Timsort-based list.sort preserve equal-key order and scale better. Quicksort is a strong general in-memory choice, while heap sort trades more writes for constant auxiliary space. Cycle sort is distinctive because it optimises a narrower dimension: changed cells can each be written once.
A compact comparison puts those trade-offs beside one another:
| Algorithm | Write profile | Typical time | Extra space | Stable | Strong fit |
|---|---|---|---|---|---|
| Cycle sort | (O(n)), with one write per changed cell | (O(n^2)) | (O(1)) | No | Write-constrained arrays |
| Insertion sort | (O(n)) best case; (O(n^2)) shifts possible | (O(n)) best, (O(n^2)) average | (O(1)) | Yes | Small or nearly sorted data |
| Merge sort | (O(n \log n)) | (O(n \log n)) | (O(n)) | Yes | Stable general-purpose sorting |
| Quicksort | (O(n \log n)) typical assignments | (O(n \log n)) average | (O(\log n)) typical | No | General in-memory sorting |
| Heap sort | (O(n \log n)) | (O(n \log n)) | (O(1)) | No | Bounded auxiliary memory |
Python list.sort |
(O(n \log n)) | (O(n \log n)) | Up to (O(n)) temporary space | Yes | Default general Python sorting |
Cycle sort is therefore a specialised answer to a specific systems problem, not a faster general substitute. When writes are expensive, the input is bounded, and stability is unnecessary, its one-write-per-changed-cell behaviour is valuable. When comparisons dominate, equal-key order matters, or the collection is large, an adaptive comparison sort usually provides the better balance.