Benchmark: Natural Sorting Methods Tested

Script Preparation code:

// Natural sort
function isNumeric(value) {
    return !isNaN(value - parseFloat(value))
}

const MAX_INT = Math.pow(2, 53)
const SAFE_STRING_INT_LENGTH = MAX_INT.toString().length - 1


function naturalSort(strA, strB) {
    const digitSplit = /(\d+)|(\D+)/g;

    // Ignore case.
    strA = strA.toLowerCase()
    strB = strB.toLowerCase()

    // Check if they're the same.
    if (strA === strB) {
        return 0;
    }

    // Split digit and non-digit sections.
    const splitA = strA.match(digitSplit)
    const splitB = strB.match(digitSplit)

    // Check every section.
    let i = 0
    while (true) {
        // Get the current section of each item.
        let splitASection = splitA[i]
        let splitBSection = splitB[i]

        // Check if we've reached the end of either string.
        let splitASecEmpty = splitASection === undefined
        let splitBSecEmpty = splitBSection === undefined

        if (splitASecEmpty && splitBSecEmpty) {
            return 0
        } else if (splitASecEmpty) {
            return -1
        } else if (splitBSecEmpty) {
            return 1
        }

        // If either section is too long to be represented as a safe integer
        // then split it and put the rest back into the array.
        if (splitASection.length > SAFE_STRING_INT_LENGTH) {
            let nextSplitA = splitASection.slice(SAFE_STRING_INT_LENGTH)
            splitASection = splitASection.slice(0, SAFE_STRING_INT_LENGTH)
            //splitA.splice(i, 1, splitASection)
            splitA.splice(i + 1, 0, nextSplitA)
        }
        if (splitBSection.length > SAFE_STRING_INT_LENGTH) {
            let nextSplitB = splitBSection.slice(SAFE_STRING_INT_LENGTH)
            splitBSection = splitBSection.slice(0, SAFE_STRING_INT_LENGTH)
            splitB.splice(i + 1, 0, nextSplitB)
        }

        // Check if either section is a number.
        let splitASecNumeric = isNumeric(splitASection)
        let splitBSecNumeric = isNumeric(splitBSection)

        if (splitASecNumeric && splitBSecNumeric) {
            splitASection = parseInt(splitASection)
            splitBSection = parseInt(splitBSection)
        } else if (splitASecNumeric) {
            return -1
        } else if (splitBSecNumeric) {
            return 1
        }

        // Compare values directly.
        if (splitASection < splitBSection) {
            return -1
        } else if (splitASection > splitBSection) {
            return 1
        }

        i++
    }
}

// Natural Compare
var naturalCompare = function(a, b) {
    var i, codeA, codeB = 1,
        posA = 0,
        posB = 0,
        alphabet = String.alphabet

    function getCode(str, pos, code) {
        if (code) {
            for (i = pos; code = getCode(str, i), code < 76 && code > 65;) ++i;
            return +str.slice(pos - 1, i)
        }
        code = alphabet && alphabet.indexOf(str.charAt(pos))
        return code > -1 ? code + 76 : ((code = str.charCodeAt(pos) || 0), code < 45 || code > 127) ? code :
            code < 46 ? 65 // -
            :
            code < 48 ? code - 1 :
            code < 58 ? code + 18 // 0-9
            :
            code < 65 ? code - 11 :
            code < 91 ? code + 11 // A-Z
            :
            code < 97 ? code - 37 :
            code < 123 ? code + 5 // a-z
            :
            code - 63
    }


    if ((a += "") != (b += ""))
        for (; codeB;) {
            codeA = getCode(a, posA++)
            codeB = getCode(b, posB++)

            if (codeA < 76 && codeB < 76 && codeA > 66 && codeB > 66) {
                codeA = getCode(a, posA, posA)
                codeB = getCode(b, posB, posA = i)
                posB = i
            }

            if (codeA != codeB) return (codeA < codeB) ? -1 : 1
        }
    return 0
}


// JavaScript Natural Sort
function javascriptNaturalSort(a, b) {
    "use strict";
    var re = /(^([+\-]?(?:0|[1-9]\d*)(?:\.\d*)?(?:[eE][+\-]?\d+)?)?$|^0x[0-9a-f]+$|\d+)/gi,
        sre = /(^[ ]*|[ ]*$)/g,
        dre = /(^([\w ]+,?[\w ]+)?[\w ]+,?[\w ]+\d+:\d+(:\d+)?[\w ]?|^\d{1,4}[\/\-]\d{1,4}[\/\-]\d{1,4}|^\w+, \w+ \d+, \d{4})/,
        hre = /^0x[0-9a-f]+$/i,
        ore = /^0/,
        i = function(s) {
            return naturalSort.insensitive && ('' + s).toLowerCase() || '' + s;
        },
        // convert all to strings strip whitespace
        x = i(a).replace(sre, '') || '',
        y = i(b).replace(sre, '') || '',
        // chunk/tokenize
        xN = x.replace(re, '\0$1\0').replace(/\0$/, '').replace(/^\0/, '').split('\0'),
        yN = y.replace(re, '\0$1\0').replace(/\0$/, '').replace(/^\0/, '').split('\0'),
        // numeric, hex or date detection
        xD = parseInt(x.match(hre), 16) || (xN.length !== 1 && x.match(dre) && Date.parse(x)),
        yD = parseInt(y.match(hre), 16) || xD && y.match(dre) && Date.parse(y) || null,
        oFxNcL, oFyNcL;
    // first try and sort Hex codes or Dates
    if (yD) {
        if (xD < yD) {
            return -1;
        } else if (xD > yD) {
            return 1;
        }
    }
    // natural sorting through split numeric strings and default strings
    for (var cLoc = 0, numS = Math.max(xN.length, yN.length); cLoc < numS; cLoc++) {
        // find floats not starting with '0', string or 0 if not defined (Clint Priest)
        oFxNcL = !(xN[cLoc] || '').match(ore) && parseFloat(xN[cLoc]) || xN[cLoc] || 0;
        oFyNcL = !(yN[cLoc] || '').match(ore) && parseFloat(yN[cLoc]) || yN[cLoc] || 0;
        // handle numeric vs string comparison - number < string - (Kyle Adams)
        if (isNaN(oFxNcL) !== isNaN(oFyNcL)) {
            return (isNaN(oFxNcL)) ? 1 : -1;
        }
        // rely on string comparison if different types - i.e. '02' < 2 != '02' < '2'
        else if (typeof oFxNcL !== typeof oFyNcL) {
            oFxNcL += '';
            oFyNcL += '';
        }
        if (oFxNcL < oFyNcL) {
            return -1;
        }
        if (oFxNcL > oFyNcL) {
            return 1;
        }
    }
    return 0;
};


// String Natural Compare
const defaultAlphabetIndexMap = [];

function isNumberCode(code) {
    return code >= 48 /* '0' */ && code <= 57 /* '9' */ ;
}

function stringNaturalCompare(a, b, opts) {
    if (typeof a !== 'string') {
        throw new TypeError(`The first argument must be a string. Received type '${typeof a}'`);
    }
    if (typeof b !== 'string') {
        throw new TypeError(`The second argument must be a string. Received type '${typeof b}'`);
    }

    const lengthA = a.length;
    const lengthB = b.length;
    let indexA = 0;
    let indexB = 0;
    let alphabetIndexMap = defaultAlphabetIndexMap;
    let firstDifferenceInLeadingZeros = 0;

    if (opts) {
        if (opts.caseInsensitive) {
            a = a.toLowerCase();
            b = b.toLowerCase();
        }

        if (opts.alphabet) {
            alphabetIndexMap = buildAlphabetIndexMap(opts.alphabet);
        }
    }

    while (indexA < lengthA && indexB < lengthB) {
        let charCodeA = a.charCodeAt(indexA);
        let charCodeB = b.charCodeAt(indexB);

        if (isNumberCode(charCodeA)) {
            if (!isNumberCode(charCodeB)) {
                return charCodeA - charCodeB;
            }

            let numStartA = indexA;
            let numStartB = indexB;

            while (charCodeA === 48 /* '0' */ && ++numStartA < lengthA) {
                charCodeA = a.charCodeAt(numStartA);
            }
            while (charCodeB === 48 /* '0' */ && ++numStartB < lengthB) {
                charCodeB = b.charCodeAt(numStartB);
            }

            if (numStartA !== numStartB && firstDifferenceInLeadingZeros === 0) {
                firstDifferenceInLeadingZeros = numStartA - numStartB;
            }

            let numEndA = numStartA;
            let numEndB = numStartB;

            while (numEndA < lengthA && isNumberCode(a.charCodeAt(numEndA))) {
                ++numEndA;
            }
            while (numEndB < lengthB && isNumberCode(b.charCodeAt(numEndB))) {
                ++numEndB;
            }

            let difference = numEndA - numStartA - numEndB + numStartB; // numA length - numB length
            if (difference !== 0) {
                return difference;
            }

            while (numStartA < numEndA) {
                difference = a.charCodeAt(numStartA++) - b.charCodeAt(numStartB++);
                if (difference !== 0) {
                    return difference;
                }
            }

            indexA = numEndA;
            indexB = numEndB;
            continue;
        }

        if (charCodeA !== charCodeB) {
            if (
                charCodeA < alphabetIndexMap.length &&
                charCodeB < alphabetIndexMap.length &&
                alphabetIndexMap[charCodeA] !== -1 &&
                alphabetIndexMap[charCodeB] !== -1
            ) {
                return alphabetIndexMap[charCodeA] - alphabetIndexMap[charCodeB];
            }

            return charCodeA - charCodeB;
        }

        ++indexA;
        ++indexB;
    }

    if (indexA < lengthA) { // `b` is a substring of `a`
        return 1;
    }

    if (indexB < lengthB) { // `a` is a substring of `b`
        return -1;
    }

    return firstDifferenceInLeadingZeros;
}

const alphabetIndexMapCache = {};

function buildAlphabetIndexMap(alphabet) {
    const existingMap = alphabetIndexMapCache[alphabet];
    if (existingMap !== undefined) {
        return existingMap;
    }

    const indexMap = [];
    const maxCharCode = alphabet.split('').reduce((maxCode, char) => {
        return Math.max(maxCode, char.charCodeAt(0));
    }, 0);

    for (let i = 0; i <= maxCharCode; i++) {
        indexMap.push(-1);
    }

    for (let i = 0; i < alphabet.length; i++) {
        indexMap[alphabet.charCodeAt(i)] = i;
    }

    alphabetIndexMapCache[alphabet] = indexMap;

    return indexMap;
}

function stringNaturalCompareCI(a, b) {
  stringNaturalCompare(a, b, { caseInsensitive: true });
}


// Alphanum-sort
var zero = '0'.charCodeAt(0);
var plus = '+'.charCodeAt(0);
var minus = '-'.charCodeAt(0);

function isWhitespace(code) {
    return code <= 32;
}

function isDigit(code) {
    return 48 <= code && code <= 57;
}

function isSign(code) {
    return code === minus || code === plus;
}

function compare(opts, a, b) {
    var checkSign = opts.sign;
    var ia = 0;
    var ib = 0;
    var ma = a.length;
    var mb = b.length;
    var ca, cb; // character code
    var za, zb; // leading zero count
    var na, nb; // number length
    var sa, sb; // number sign
    var ta, tb; // temporary
    var bias;

    while (ia < ma && ib < mb) {
        ca = a.charCodeAt(ia);
        cb = b.charCodeAt(ib);
        za = zb = 0;
        na = nb = 0;
        sa = sb = true;
        bias = 0;

        // skip over leading spaces
        while (isWhitespace(ca)) {
            ia += 1;
            ca = a.charCodeAt(ia);
        }
        while (isWhitespace(cb)) {
            ib += 1;
            cb = b.charCodeAt(ib);
        }

        // skip and save sign
        if (checkSign) {
            ta = a.charCodeAt(ia + 1);
            if (isSign(ca) && isDigit(ta)) {
                if (ca === minus) {
                    sa = false;
                }
                ia += 1;
                ca = ta;
            }
            tb = b.charCodeAt(ib + 1);
            if (isSign(cb) && isDigit(tb)) {
                if (cb === minus) {
                    sb = false;
                }
                ib += 1;
                cb = tb;
            }
        }

        // compare digits with other symbols
        if (isDigit(ca) && !isDigit(cb)) {
            return -1;
        }
        if (!isDigit(ca) && isDigit(cb)) {
            return 1;
        }

        // compare negative and positive
        if (!sa && sb) {
            return -1;
        }
        if (sa && !sb) {
            return 1;
        }

        // count leading zeros
        while (ca === zero) {
            za += 1;
            ia += 1;
            ca = a.charCodeAt(ia);
        }
        while (cb === zero) {
            zb += 1;
            ib += 1;
            cb = b.charCodeAt(ib);
        }

        // count numbers
        while (isDigit(ca) || isDigit(cb)) {
            if (isDigit(ca) && isDigit(cb) && bias === 0) {
                if (sa) {
                    if (ca < cb) {
                        bias = -1;
                    } else if (ca > cb) {
                        bias = 1;
                    }
                } else {
                    if (ca > cb) {
                        bias = -1;
                    } else if (ca < cb) {
                        bias = 1;
                    }
                }
            }
            if (isDigit(ca)) {
                ia += 1;
                na += 1;
                ca = a.charCodeAt(ia);
            }
            if (isDigit(cb)) {
                ib += 1;
                nb += 1;
                cb = b.charCodeAt(ib);
            }
        }

        // compare number length
        if (sa) {
            if (na < nb) {
                return -1;
            }
            if (na > nb) {
                return 1;
            }
        } else {
            if (na > nb) {
                return -1;
            }
            if (na < nb) {
                return 1;
            }
        }

        // compare numbers
        if (bias) {
            return bias;
        }

        // compare leading zeros
        if (sa) {
            if (za > zb) {
                return -1;
            }
            if (za < zb) {
                return 1;
            }
        } else {
            if (za < zb) {
                return -1;
            }
            if (za > zb) {
                return 1;
            }
        }

        // compare ascii codes
        if (ca < cb) {
            return -1;
        }
        if (ca > cb) {
            return 1;
        }

        ia += 1;
        ib += 1;
    }

    // compare length
    if (ma < mb) {
        return -1;
    }
    if (ma > mb) {
        return 1;
    }
};

function mediator(a, b) {
    return compare(this, a.converted, b.converted);
}

function alphanumSort(array, opts) {
    if (!Array.isArray(array) || array.length < 2) {
        return array;
    }
    if (typeof opts !== 'object') {
        opts = {};
    }
    opts.sign = !!opts.sign;
    var insensitive = !!opts.insensitive;
    var result = Array(array.length);
    var i, max, value;

    for (i = 0, max = array.length; i < max; i += 1) {
        value = String(array[i]);
        result[i] = {
            value: array[i],
            converted: insensitive ? value.toLowerCase() : value
        };
    }

    result.sort(mediator.bind(opts));

    for (i = result.length - 1; ~i; i -= 1) {
        result[i] = result[i].value;
    }

    return result;
};

Tests:

Natural Sort
const arr = ['20', '2c', '2a', '1-3bench', 'test12', 'test5', 'TEST9', '1.6', '1.A6', "90071992547400029999", "90071992547400021111", "Test42"] console.log(arr.sort(naturalSort))
Natural Compare
const arr = ['20', '2c', '2a', '1-3bench', 'test12', 'test5', 'TEST9', '1.6', '1.A6', "90071992547400029999", "90071992547400021111", "Test42"] console.log(arr.sort(naturalCompare))
JavaScript Natural Sort
const arr = ['20', '2c', '2a', '1-3bench', 'test12', 'test5', 'TEST9', '1.6', '1.A6', "90071992547400029999", "90071992547400021111", "Test42"] console.log(arr.sort(javascriptNaturalSort))
String Natural Compare
const arr = ['20', '2c', '2a', '1-3bench', 'test12', 'test5', 'TEST9', '1.6', '1.A6', "90071992547400029999", "90071992547400021111", "Test42"] console.log(arr.sort(stringNaturalCompareCI))
Alphanum-Sort
const arr = ['20', '2c', '2a', '1-3bench', 'test12', 'test5', 'TEST9', '1.6', '1.A6', "90071992547400029999", "90071992547400021111", "Test42"] console.log(alphanumSort([].concat(arr), { insensitive: true }))

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Natural Sort
Natural Compare
JavaScript Natural Sort
String Natural Compare
Alphanum-Sort

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 25 days ago):

LLMs can make mistakes. Check important info.

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/105.0.0.0 Safari/537.36 Edg/105.0.1343.33

Browser/OS: Chrome 105 on Windows

View result in a separate tab

Test name	Executions per second
Natural Sort	10770.2 Ops/sec
Natural Compare	35536.2 Ops/sec
JavaScript Natural Sort	7091.7 Ops/sec
String Natural Compare	35940.8 Ops/sec
Alphanum-Sort	8379.2 Ops/sec

Related benchmarks:

Natural Sorting Methods Tested (version: 0)

Comparing performance of: Natural Sort vs Natural Compare vs JavaScript Natural Sort vs String Natural Compare vs Alphanum-Sort

Created: 2 years ago by: Guest

Jump to the latest result

Natural Sort

Natural Compare

JavaScript Natural Sort

String Natural Compare

Alphanum-Sort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 25 days ago):