Károly Lőrentey (via Nick Lockwood): The benchmark above demonstrates this really well: insertion into a sorted array is O(n^2) when there are many items, but it is still much faster than a red-black tree with its attractive-looking O(n * log(n)) solution. At the beginning of the curve, up to about eighteen thousand items, a sorted … Continue reading Fast Ordered Collections for Swift Using In-memory B-trees