twosorted

Twosorted is a term used in data processing and algorithm design to describe the practice of sorting two related sequences in tandem, so that the correspondence between elements is preserved. The core idea is to rearrange elements of both sequences together according to a chosen primary sort criterion applied to one of the sequences, ensuring that the pairing between the two is maintained.

A common implementation method is to construct a sequence of paired elements, such as P[i] = (A[i], B[i]), then sort the pair sequence by the first component A[i] using a stable sorting algorithm. After sorting, the values can be unpacked back into the two separate sequences, now in synchronized order. An alternative approach is to compute a permutation that describes the required order and apply it to both sequences, which can be more memory efficient in some cases.

Twosorted results in time complexity of O(n log n) with extra memory proportional to the number of elements if pairs are created. In-place variants exist but require more intricate index manipulation. Stability matters when preserving the relative order of equal keys, and a two-step approach using stable sorts on multiple keys can achieve multi-field sorting.

Applications include aligning two related datasets, such as a list of keys with corresponding values, or sorting records by a primary key while carrying along secondary fields. It is distinct from sorting two sequences independently, which can break the original relationships between corresponding elements.

See also: stable sort, pair sorting, key-value sorting, multi-key sort. Example: A = [3, 1, 2], B = ['x','y','z']; after twosort by A, A = [1, 2, 3], B = ['y','z','x'].