Proposal: slice together two arrays with sortFn

[KieranP]

Naive push/sort approach:

items.push(...newItems)
items.sort(sortFn)

This can be slow though when going over 10,000 items.

Proposing a new splice function (LLM generated code):

function slice(existing: any[], newItems: any[], sortFn: (a: any, b: any) => number) {
  newItems.sort(sortFn)

  let searchIndex = 0

  for (const item of newItems) {
    let inserted = false
    for (let i = searchIndex; i < existing.length; i++) {
      if (sortFn(item, existing[i]) <= 0) {
        existing.splice(i, 0, item)
        searchIndex = i + 1
        inserted = true
        break
      }
    }
    if (!inserted) {
      existing.push(item)
      searchIndex = existing.length
    }
  }

  return existing
}

import { splice } from 'es-toolkit'

const items = [
  { publishedAt: new Date("2025-01-10") },
  // ...
]

const newItems = [
  { publishedAt: new Date("2025-01-01") },
  // ...
]

splice(items, newItems, (a, b) => b.publishedAt - a.publishedAt)

// items now has newItems inserted at the right sorted location

Benchmarks:

Running benchmark with batch size: 10

--- Array Size: 10 (1000 iterations) ---
Push & Sort:       1.17ms
Presort & Splice:  1.22ms

--- Array Size: 100 (1000 iterations) ---
Push & Sort:       2.73ms
Presort & Splice:  2.15ms

--- Array Size: 1000 (1000 iterations) ---
Push & Sort:       30.06ms
Presort & Splice:  12.47ms

--- Array Size: 10000 (100 iterations) ---
Push & Sort:       30.03ms
Presort & Splice:  14.25ms

Running benchmark with batch size: 50

--- Array Size: 10 (1000 iterations) ---
Push & Sort:       4.29ms
Presort & Splice:  4.69ms

--- Array Size: 100 (1000 iterations) ---
Push & Sort:       6.74ms
Presort & Splice:  5.49ms

--- Array Size: 1000 (1000 iterations) ---
Push & Sort:       38.65ms
Presort & Splice:  14.41ms

--- Array Size: 10000 (100 iterations) ---
Push & Sort:       27.90ms
Presort & Splice:  10.93ms