Sorting

Benchmark created on September 11, 2024

Setup

const items = Array.from({ length: 100e3 }).map(() => {
  const age = Math.floor(Math.random() * 4294967295)
  return {
    age,
    name: 'Youzi ' + age,
  }
})


const ultrasort = (items, key) => {
  let i = items.length
  let j = 0
  const map = {}
  const res = Array(i)
  let size = 256
  let tmp = new Uint8Array(i)

  while (i--) {
    const v = items[i][key]
    if (v in map) {
      map[v].push(i)
    } else {
      if (v >= size) {
        size += size
        tmp = size === 65535 ? new Uint16Array(tmp) : new Uint32Array(tmp)
      }
      tmp[j] = v
      map[v] = [i]
      j++
    }
  }

  // sort the values
  const srt = tmp.subarray(0, j).sort()
  for (const v of srt) {
    for (const idx of map[v]) {
      res[++i] = items[idx]
    }
  }

  return res
}

const sortA = (items, key) => {
  const map = {}
  for (const item of items) {
    const val = item[key]
  }
}


const megasortZ = (items, key) => {
  const map = {}
  let l = items.length
  let uint8
  let uint16
  let uint32
  let j = l
  const sorted = Array(l)
  for (const item of items) {
    const n = item[key]
    if (n in map) {
      map[n].push(item)
    } else {
      map[n] = [item]
      if (n <= 255) {
        if (uint8 === undefined) {
          uint8 = new Uint8Array(l)
          uint8.i = 0
        }
        uint8[uint8.i++] = n
      } else if (n <= 65535) {
        if (uint16 === undefined) {
          uint16 = new Uint16Array(l)
          uint16.i = 0
        }
        uint16[uint16.i++] = n
      } else if (n <= 4294967295) {
        if (uint32 === undefined) {
          uint32 = new Uint32Array(l)
          uint32.i = 0
        }
        uint32[uint32.i++] = n
      } else {
        sorted[--j] = n
      }
    }
    l--
  }

  let i = 0
  if (uint8) {
    uint8 = uint8.subarray(0, uint8.i).sort()
    for (const n of uint8) {
      for (const item of map[n]) {
        sorted[i++] = item
      }
    }
  }

  if (uint16) {
    uint16 = uint16.subarray(0, uint16.i).sort()
    for (const n of uint16) {
      for (const item of map[n]) {
        sorted[i++] = item
      }
    }
  }

  if (uint32) {
    uint32 = uint32.subarray(0, uint32.i).sort()
    for (const n of uint32) {
      for (const item of map[n]) {
        sorted[i++] = item
      }
    }
  }

  return sorted
}

const sortB = (items, key) => {
  const map = {}
  const k = key
  for (const item of items) {
    const val = item[k]
  }
}

const megasort = (items, key) => {
  let i = items.length
  let j = 0
  const cnt = {}
  const map = {}
  const res = Array(i)

  // count first
  for (const item of items) {
    const v = item[key]
    if (v in cnt) {
      cnt[v][0]++
    } else {
      const arr = new Uint32Array(2)
      arr[0] = 1
      arr[1] = v
      cnt[v] = arr
      j++
    }
  }

  // init the map and the tmp arr
  const tmp = new Uint32Array(j)
  for (const val in cnt) {
    const [l, v] = cnt[val]
    map[v] = new Uint32Array(l)
    tmp[--j] = v
  }

  // fill the map with the indexes
  while (i--) {
    const val = items[i][key]
    map[val][--cnt[val][0]] = i
  }

  // sort the values
  tmp.sort()

  for (const v of tmp) {
    for (const idx of map[v]) {
      res[j++] = items[idx]
    }
  }

  return res
}

const megasort2 = (items, key) => {
  let i = items.length
  let j = 0
  const map = {}
  const res = Array(i)
  const tmp = new Uint32Array(i)

  // count first
  while (i--) {
    const v = items[i][key]
    if (v in map) {
      map[v].push(i)
    } else {
      tmp[j] = v
      map[v] = [i]
      j++
    }
  }

  // sort the values
  const srt = tmp.subarray(0, j).sort()
  for (const v of srt) {
    for (const idx of map[v]) {
      res[++i] = items[idx]
    }
  }

  return res
}

const megasort3 = (items, key) => {
  let i = items.length
  let j = 0
  let s = i
  const map = {}
  const res = Array(i)
  let uint8, uint16, uint32
  // count first
  while (i--) {
    const v = items[i][key]
    if (v in map) {
      map[v].push(i)
    } else {
      map[v] = [i]
      if (v <= 255) {
        if (uint8 === undefined) {
          uint8 = new Uint8Array(i + 1)
          uint8.i = 0
        }
        uint8[uint8.i++] = v
      } else if (v <= 65535) {
        if (uint16 === undefined) {
          uint16 = new Uint16Array(i + 1)
          uint16.i = 0
        }
        uint16[uint16.i++] = v
      } else if (v <= 4294967295) {
        if (uint32 === undefined) {
          uint32 = new Uint32Array(i + 1)
          uint32.i = 0
        }
        uint32[uint32.i++] = v
      } else {
        res[--s] = v
      }
      j++
    }
  }

  // sort the values
  if (uint8) {
    uint8 = uint8.subarray(0, uint8.i).sort()
    for (const n of uint8) {
      for (const idx of map[n]) {
        res[++i] = items[idx]
      }
    }
  }

  if (uint16) {
    uint16 = uint16.subarray(0, uint16.i).sort()
    for (const n of uint16) {
      for (const idx of map[n]) {
        res[++i] = items[idx]
      }
    }
  }

  if (uint32) {
    uint32 = uint32.subarray(0, uint32.i).sort()
    for (const n of uint32) {
      for (const idx of map[n]) {
        res[++i] = items[idx]
      }
    }
  }

  return res
}

Test runner

const sorted = Array.from(items).sort((a, b) => a.age < b.age ? -1 : 1)

const sorted = megasort(items, 'age')

const sorted = megasort2(items, 'age')

const sorted = megasort3(items, 'age')

const sorted = megasortZ(items, 'age')

const sorted = ultrasort(items, 'age')

Revisions

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

• Revision 1: published on September 11, 2024