bigSorting.js

// source: https://www.hackerrank.com/challenges/big-sorting/problem
// video: https://youtu.be/0KJhHCIuoG0
function bigSorting(unsorted) {
    // Chunk values into separate sizes
    const cache = {}
    
    for (const val of unsorted){ // O(n), max of 2*10^5
        const length = val.length
        if (!cache[length]){
            cache[length] = []
        }
        cache[length].push(val)
    }
    // Sort the lengths
    const sizes = Object.keys(cache).sort((a,b)=>parseInt(a)-parseInt(b)) // O(10^6) = O(1)
    let output = []
    // For each length, sort it's list and add to growing output list
    for (const size of sizes){ // O(10^6) = O(1)
        const vals = cache[size]
        vals.sort() // O(nlogn) where n is the size of the list (max of 2*10^5)
        output = [...output, ...vals]
    }
    return output // O(n) + O(nlogn) = O(nlogn)
}