LazySort How-To Guide

LazySort is designed to retrieve elements by index from an unsorted dataset as if the dataset were fully sorted, without sorting the entire dataset or consuming excessive memory.
It is ideal when sorting the entire dataset is impractical, but specific indexed elements (such as the median or a specific percentile) need to be retrieved. Additionally, it can determine the index of an element in the sorted representation of the dataset.

Overview

The core algorithm consists of two phases:

1. Analysis & Clustering: Analyzes the raw dataset and partitions it into indexed clusters.
2. In-Memory Sort & Retrieval: Loads and sorts only the single cluster containing the requested element, then returns the target item.

If a cluster containing the requested item exceeds the user-defined memory limit, it is dynamically re-partitioned into smaller sub-clusters.

Installation

Using pip:

pip install lazysort

Using uv:

uv add lazysort

Source code available at gitlab.com/daemn/lazysort

Usage

from lazysort import LazySort # An unsorted dataset. data = [42, 15, 8, 23, 4, 16, 99, 51, 3] # Wrap the dataset with LazySort. # work_items_limit defines the maximum number of elements loaded into memory. ls = LazySort(data, work_items_limit=4) # Access elements as if the collection were sorted. print(ls[0]) # Output: 3 print(ls[1]) # Output: 4 print(ls[-1]) # Output: 99 # Slicing is also fully supported. print(tuple(ls[2:6])) # Iteration yields elements in sorted order. for item in ls: print(item) # Using a custom key function and reverse sorting complex_ls = LazySort(data, work_items_limit=4, key_fn=lambda x: x, reverse=True)

Demo Walkthrough

To demonstrate functionality, a 10 GB test file containing 10 million random 1024-byte items was generated.
Dataset Generator Script:

import random with open('random_data.bin', 'wb') as fd:     for _ in range(10_000_000):         fd.write(random.randbytes(1024))

File Sequence Reader

To access elements from the raw binary file, a simple SequenceReader wrapper was implemented:

from collections.abc import Iterator, Iterable from pathlib import Path from typing import BinaryIO, Self, overload class SequenceReader:     _file: Path     _fd: BinaryIO     _item_size: int     def __init__(self, file: Path, item_size: int) -> None:         self._file = file         self._item_size = item_size     def __enter__(self) -> Self:         self._fd = self._file.open('rb')         return self     def __exit__(self, exc_type, exc_val, exc_tb) -> None:         self._fd.close()     def __len__(self) -> int:         return self._file.stat().st_size // self._item_size     @overload     def __getitem__(self, item: int, /) -> bytes: ...     @overload     def __getitem__(self, item: slice, /) -> Iterable[bytes]: ...     def __getitem__(self, item: int | slice, /) -> bytes | Iterable[bytes]:         if isinstance(item, int):             return self._getitem(item)         return (self._getitem(i) for i in range(             item.start or 0,             item.stop or self.__len__(),             item.step or 1         ))     def _getitem(self, item: int) -> bytes:         self._fd.seek(item * self._item_size)         return self._fd.read(self._item_size)     def __iter__(self) -> Iterator[bytes]:         self._fd.seek(0)         while item := self._fd.read(self._item_size):             yield item

LazySort Execution

We configured LazySort with work_items_limit=100_000. This limits in-memory sorting overhead to ~100 MB of data, plus ~400 KB for cluster metadata.
Each cluster is tracked by integer metadata and two boundary elements (minimum and maximum). The maximum number of clusters is determined by:
max_clusters = (total_items // work_items_limit) * 2 (For 10,000,000 items with a limit of 100,000, 200 clusters are created).

from lazysort import LazySort with SequenceReader(Path('random_data.bin'), item_size=1024) as src_data:     ls = LazySort(src_data, work_items_limit=100_000)     print(ls[0])     print(ls[1_000])     print(ls[9_500_000])     print(ls[9_999_999])     print(ls[1_000])

Performance & Memory Footprint

The chart below illustrates process memory consumption (resident memory) alongside disk read operations across execution phases:

Phase I: Initial Access (get 0 & get 1,000)

Initialization: Instantiating LazySort does not trigger dataset analysis. Memory starts at ~20 MB (Python interpreter and script overhead).

First Query (get 0): Dataset analysis runs on-demand. The algorithm identifies the cluster containing index 0: {"idx": 0, "size": 38752}.

In-Memory Sort: Since 38,752 <= 100,000, the cluster (39 MB) is loaded into memory and sorted. Total RAM usage reaches ~60 MB (~20 MB Python + ~39 MB data). Item 0 is returned.

Cache Hit (get 1,000): Index 1,000 resides in the already loaded cluster {"idx": 0, "size": 38752}. No disk I/O is required, returning the element instantly.

Phase II: Partitioning Large Clusters (get 9,500,000)

Query get 9,500,000: The target cluster {"idx": 9454757, "size": 179435} exceeds the 100,000-item limit.

Re-clustering: LazySort re-analyzes and splits this cluster into two smaller sub-clusters: {"idx": 9454757, "size": 96520} and {"idx": 9551277, "size": 82915}.

Target Load: The first sub-cluster (96,520 items / ~97 MB) contains index 9,500,000. It is loaded and sorted, bringing total memory usage to ~125 MB.

Phase III: High-Index Retrieval (get 9,999,999)

Query get 9,999,999: The target cluster {"idx": 9910300, "size": 89700} is within the memory limit. It is loaded and sorted, using ~120 MB RAM.

Phase IV: Re-loading Previous Cluster (get 1,000)

Query get 1,000: Cluster {"idx": 0, "size": 38752} is loaded and sorted again as in Phase I, using ~60 MB RAM.