Problem. Merging closed intervals is easy to state and surprisingly easy to make quadratic. The input can arrive in any order, while a baseline that scans the accumulated output after every new interval keeps revisiting the same ranges. Baseline. merge_rescan() builds a disjoint result by scanning current ranges and restarting after each overlap. Its worst-case work is O(n²), followed by a final sort. Solution. merge_sorted() orders intervals once with Python’s sorted(), then makes one forward pass. The sort returns a new list, so the input sequence remains untouched.[1] Measured result. On CPython 3.13.5 and a Raspberry Pi aarch64 host, the n = 1,024 run took 72.936 ms for the rescan baseline and 0.763 ms for sort and sweep, a 95.61x median gap. Both returned 266 merged ranges. The traced peak was 66.8 KiB versus 32.8 KiB.
Reproduce the result
Complete code
from __future__ import annotationsimport gcimport jsonimport platformimport randomimport statisticsimport sysimport timeitimport tracemallocSEED = 20261016SIZES = (64, 128, 256, 512, 1024)REPEATS = 5WARMUPS = 1def merge_rescan(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]: """Merge closed intervals by scanning the current result for each input.""" pending = [(start, end) for start, end in intervals] merged: list[tuple[int, int]] = [] while pending: start, end = pending.pop() index = 0 while index < len(merged): other_start, other_end = merged[index] if start <= other_end and other_start <= end: start = min(start, other_start) end = max(end, other_end) merged.pop(index) index = 0 else: index += 1 merged.append((start, end)) return sorted(merged)def merge_sorted(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]: """Merge closed intervals after sorting them by start and end.""" ordered = sorted(intervals) if not ordered: return [] merged = [ordered[0]] for start, end in ordered[1:]: previous_start, previous_end = merged[-1] if start <= previous_end: if end > previous_end: merged[-1] = (previous_start, end) else: merged.append((start, end)) return mergeddef make_intervals(size: int) -> list[tuple[int, int]]: rng = random.Random(SEED + size) domain = size * 20 maximum_length = size // 20 + 4 return [ (start, start + rng.randrange(1, maximum_length)) for start in (rng.randrange(domain) for _ in range(size)) ]def timed_samples(function, intervals: list[tuple[int, int]]) -> list[float]: timer = timeit.Timer(lambda: function(intervals)) return [sample * 1000 for sample in timer.repeat(repeat=REPEATS, number=1)]def peak_kib(function, intervals: list[tuple[int, int]]) -> float: gc.collect() if tracemalloc.is_tracing(): tracemalloc.stop() tracemalloc.start() tracemalloc.reset_peak() try: function(intervals) _, peak = tracemalloc.get_traced_memory() finally: tracemalloc.stop() return peak / 1024def run() -> list[dict[str, object]]: boundary_cases = [ [], [(1, 2)], [(1, 3), (3, 5), (10, 12)], [(8, 9), (1, 20), (4, 6), (21, 22)], ] for case in boundary_cases: if merge_rescan(case) != merge_sorted(case): raise AssertionError(f"boundary mismatch: {case!r}") records = [] for size in SIZES: intervals = make_intervals(size) expected = merge_sorted(intervals) if merge_rescan(intervals) != expected: raise AssertionError(f"differential mismatch at size {size}") for _ in range(WARMUPS): merge_rescan(intervals) merge_sorted(intervals) naive_samples = timed_samples(merge_rescan, intervals) sorted_samples = timed_samples(merge_sorted, intervals) naive_peak = peak_kib(merge_rescan, intervals) sorted_peak = peak_kib(merge_sorted, intervals) records.append( { "size": size, "merged": len(expected), "naive_samples_ms": naive_samples, "sorted_samples_ms": sorted_samples, "naive_median_ms": statistics.median(naive_samples), "sorted_median_ms": statistics.median(sorted_samples), "speedup": statistics.median(naive_samples) / statistics.median(sorted_samples), "naive_peak_kib": naive_peak, "sorted_peak_kib": sorted_peak, } ) return recordsdef main() -> None: records = run() print(f"python={platform.python_implementation()} {sys.version.split()[0]}") print(f"platform={platform.platform()}") print(f"machine={platform.machine()}") print(f"seed={SEED} sizes={','.join(map(str, SIZES))}") print(f"warmups={WARMUPS} repeats={REPEATS} timer=timeit.default_timer number=1") print("correctness=PASS boundary_cases=4 differential_sizes=5") for record in records: print( "size={size} merged={merged} " "rescan_median_ms={naive_median_ms:.3f} " "sorted_median_ms={sorted_median_ms:.3f} " "speedup={speedup:.2f}x " "rescan_peak_kib={naive_peak_kib:.1f} " "sorted_peak_kib={sorted_peak_kib:.1f}".format(**record) ) print(" rescan_samples_ms=" + json.dumps([round(x, 3) for x in record["naive_samples_ms"]])) print(" sorted_samples_ms=" + json.dumps([round(x, 3) for x in record["sorted_samples_ms"]]))if __name__ == "__main__": main()
Command
python3 interval_merge_benchmark.py
Captured output
python=CPython 3.13.5platform=Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41machine=aarch64seed=20261016 sizes=64,128,256,512,1024warmups=1 repeats=5 timer=timeit.default_timer number=1correctness=PASS boundary_cases=4 differential_sizes=5size=64 merged=56 rescan_median_ms=0.419 sorted_median_ms=0.034 speedup=12.18x rescan_peak_kib=4.7 sorted_peak_kib=4.7 rescan_samples_ms=[0.436, 0.42, 0.401, 0.419, 0.401] sorted_samples_ms=[0.059, 0.036, 0.034, 0.034, 0.033]size=128 merged=103 rescan_median_ms=1.498 sorted_median_ms=0.074 speedup=20.30x rescan_peak_kib=8.9 sorted_peak_kib=8.6 rescan_samples_ms=[1.522, 1.51, 1.476, 1.498, 1.475] sorted_samples_ms=[0.083, 0.074, 0.074, 0.072, 0.071]size=256 merged=170 rescan_median_ms=5.927 sorted_median_ms=0.164 speedup=36.11x rescan_peak_kib=17.0 sorted_peak_kib=14.8 rescan_samples_ms=[5.901, 7.637, 6.254, 5.898, 5.927] sorted_samples_ms=[0.189, 0.167, 0.164, 0.163, 0.163]size=512 merged=248 rescan_median_ms=21.019 sorted_median_ms=0.363 speedup=57.90x rescan_peak_kib=33.7 sorted_peak_kib=23.8 rescan_samples_ms=[21.159, 21.019, 20.875, 20.948, 21.19] sorted_samples_ms=[0.387, 0.488, 0.363, 0.358, 0.357]size=1024 merged=266 rescan_median_ms=72.936 sorted_median_ms=0.763 speedup=95.61x rescan_peak_kib=66.8 sorted_peak_kib=32.8 rescan_samples_ms=[72.32, 73.826, 72.936, 73.204, 72.633] sorted_samples_ms=[0.827, 0.763, 0.758, 0.755, 0.771]
Environment and versions
The run used CPython 3.13.5, Linux 6.12.47+rpt-rpi-v8, aarch64 hardware and the Python standard library only. timeit.Timer.repeat() supplied five one-call samples per function, using Python’s default performance counter.[2]
The input generator creates a separate random.Random instance for each size from the fixed seed 20261016. The instances do not share state. The captured construction is repeatable with this CPython version and source; Python documents that seeding behaviour can change between versions.[4]
Methodology
Each case contains integer closed intervals. Two intervals overlap when the next start is less than or equal to the current end, so touching endpoints are merged. Sizes are 64, 128, 256, 512 and 1,024. One warm-up call runs before measurement. The benchmark checks the complete returned interval list from both functions before it records timings.
The timer records five samples with number=1. Python’s timeit temporarily disables garbage collection during a timing run, which makes the two function calls more comparable but leaves collection cost outside this measurement.[2] The input list is generated before timing, so input construction is excluded from the reported milliseconds.
For memory, tracemalloc starts immediately before each function call, resets its peak counter, and stops after the result is returned. The values therefore describe traced Python allocations made during the call. They exclude the already-built input, interpreter startup, native allocations and process RSS.[3]
Limits of the experiment
The result comes from one CPython build, one aarch64 host and one pseudo-random interval distribution. The generator changes maximum interval length as n grows, so the larger cases change overlap density as well as input count. Different distributions, input orders, Python implementations, CPU loads and sizes can change the absolute timings. The comparison does not measure database queries, file input, network traffic, concurrent updates or a streaming interval index.
The functions assume each pair has start <= end, merge closed integer pairs and discard any metadata attached to an interval. Half-open ranges, time zones, CIDR prefixes and records that need to retain their original identifiers require a different interface. The measured peak is a tracemalloc statistic, not a whole-process memory reading.
The problem
A useful interval merger returns non-overlapping ranges that cover the same points as the input union. The awkward part is keeping that invariant while intervals arrive unsorted. A new interval can overlap one saved range, several saved ranges, or a range created by merging the first two. The baseline handles that last case by starting its scan again.
That restart is where the extra work comes from. With many saved ranges, every new interval may inspect most of them. The code remains correct, but the number of comparisons grows with both the input size and the size of the partial result.
Baseline: rescan
merge_rescan() keeps a pending list and a result list. It removes one interval, compares it with each saved range, absorbs every overlap, and restarts from the beginning whenever the active range grows. After all input has been consumed, it sorts the result so callers receive a predictable order.
The implementation has a useful teaching property: every operation is visible. It also exposes the cost of postponing order. With many disjoint saved ranges, a later interval can scan almost all of them. That comparison pattern is quadratic in the input size; the captured run uses the generated distribution described above rather than a constructed worst-case input. The final result sort adds O(n log n) work.
Solution: sort and sweep
merge_sorted() asks sorted() to put intervals in start order. The first interval becomes the active range. Each later interval starts at or before the active end and may extend that range, or starts after the active end and begins a new one. A contained or duplicate interval leaves the active end unchanged.
The active range is enough because sorted order has already ruled out every earlier interval. The algorithm spends O(n log n) work ordering the input and O(n) work walking it. It also keeps the original list unchanged because sorted() builds a separate list.[1]
The choice of closed intervals controls one small detail. (1, 3) and (3, 5) share endpoint 3, so the code emits (1, 5). A half-open representation would use a strict comparison and would keep those ranges separate.
What the measurement shows
The four boundary cases are checked before timing, and each generated size is checked immediately before its own measurements. The median speedup grew from 12.18x at 64 intervals to 95.61x at 1,024. The individual samples are retained in the Output block, including a slower rescan sample at size 256 rather than being replaced by a cleaner-looking number.
At n = 1,024, both implementations returned 266 ranges. The sort-and-sweep median was 0.763 ms, against 72.936 ms for the rescan baseline. Its traced peak was also lower, 32.8 KiB against 66.8 KiB. Those memory values reflect the allocations made inside these two Python functions; they do not establish a memory ratio for another interval representation.
The curve is the result of this generator and this host. It shows the expected effect of repeated scans becoming more expensive as the partial result grows. It does not turn one local run into a promise about every interval workload.
Practical applications
Calendar and booking windows
A booking service can represent occupied slots as integer minute ranges, sort them by start time and merge overlaps before checking availability. The sweep fits a batch reconciliation step. A live scheduler receiving one change at a time may need an ordered index instead, and date arithmetic still needs an explicit time-zone policy.
Network and address ranges
A firewall or routing tool can coalesce numeric address ranges before applying a rule set. Sorting reduces repeated comparisons when a configuration contains many overlapping entries. CIDR prefixes carry boundary and prefix-length semantics, so converting them to intervals can lose policy information unless the conversion is deliberate.
Logs, alerts and batch windows
An event pipeline can merge alert windows before grouping notifications or scheduling a batch job. The benchmark’s integer pairs model the coalescing step, not the storage or delivery system around it. A stream that must answer queries between arrivals needs an incremental structure rather than rebuilding a sorted list for every event.
These applications are broader engineering uses of the same invariant. The benchmark measures only in-memory integer intervals, and it does not measure any of the services described above.
Sources
[1] Built-in Functions: sorted | Python 3.13 documentation
[2] timeit | Python 3.13 documentation
