I did some quick benchmarks the other day between sorted array vs red black tree of https://github.com/preludejs https://github.com/preludejs and it looked like

I did some quick benchmarks the other day between sorted array vs red black tree of https://github.com/preludejs https://github.com/preludejs and it looked like rb tree had better generic performance for N > 20k - ie. memcpy is better for most cases/cases that fall under 20k. You should measure of course for your use case. Libraries/your implementation should make it easy to switch between underlying representation.