Sort By Cursor

Benchmark created on October 3, 2025

Setup

var sortedData = []
for (let i = 0; i < 1e3; i++) {
    sortedData.push({id: i + 1, next: i + 2})
}
sortedData.at(-1).next = null

var data = sortedData
    .map(value => ({ value, sort: Math.random() }))
    .sort((a, b) => a.sort - b.sort)
    .map(({ value }) => value)

function sortByCursor(data, getId, getNext) {
    const length = data.length;
    const map = new Map();
    let lastItem = null;
    // Single loop: build map and find last item
    for (let i = 0; i < length; i++) {
        const record = data[i];
        const next = getNext(record);
        if (next === null)
            lastItem = record;
        else
            map.set(next, record);
    }
    if (lastItem === null)
        throw new Error('unable to sort an array that has no last item');
    // Pre-allocate array and use direct assignment
    const result = new Array(length);
    let current = lastItem;
    let i = length;
    // Follow chain with decrementing index
    while (i--) {
        result[i] = current;
        if (current === undefined)
            break;
        current = map.get(getId(current));
        if (current === undefined)
            break;
    }
    return result;
}

Test runner

const result = sortByCursor(data, item => item.id, item => item.next)

const result = data.toSorted((a,b) => a.id - b.id)

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on October 3, 2025