# Sorted Array implementation?

**URL:** <https://discourse.julialang.org/t/sorted-array-implementation/5897>\
**Category:** General Usage\
**Tags:** array, sort\
**Created:** [September 15, 2017, 12:05am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897 "2017-09-15T00:05:51Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![raff](https://avatars.discourse-cdn.com/v4/letter/r/5e9695/32.png) [@raff](https://discourse.julialang.org/u/raff)\
**Post date:** [September 15, 2017, 12:05am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/1 "2017-09-15T00:05:51Z")

</div>

Is there any implementation of sorted array?  
I need to store a sorted list of integer. I will frequently check what is the k-th value in the list and in what position a particular value is in the list.  
I checked SortedSet in DataStructures.jl, but it seems that it does not have easy way to do these tasks.

---

<div class="post-metadata">

**Author:** ![garrison](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/garrison/32/209519_2.png) [@garrison](https://discourse.julialang.org/u/garrison)\
**Post date:** [September 15, 2017, 2:59am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/2 "2017-09-15T02:59:55Z")

</div>

There is `sort!`, which can of course be used to sort any ~~array~~ vector. Precisely what are the shortcomings you need to be addressed? Do you need to mutate the array over time, while expecting it remains sorted? Do you have big-O efficiency requirements for certain operations (insertion, deletion, lookup, etc.)?

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 15, 2017, 3:43am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/3 "2017-09-15T03:43:34Z")

</div>

DataStructures.jl has `SortedSet` if you don’t mind not having duplicates:

```julia
julia> using DataStructures

julia> s = SortedSet{Int}()
SortedSet(Int64[],
Base.Order.ForwardOrdering())

julia> push!(s,10)
SortedSet([10],
Base.Order.ForwardOrdering())

julia> push!(s,2)
SortedSet([2, 10],
Base.Order.ForwardOrdering())

julia> push!(s,4)
SortedSet([2, 4, 10],
Base.Order.ForwardOrdering())

julia> push!(s,9)
SortedSet([2, 4, 9, 10],
Base.Order.ForwardOrdering())

julia> collect(s)
4-element Array{Int64,1}:
  2
  4
  9
 10

```

---

<div class="post-metadata">

**Author:** ![raff](https://avatars.discourse-cdn.com/v4/letter/r/5e9695/32.png) [@raff](https://discourse.julialang.org/u/raff)\
**Post date:** [September 15, 2017, 4:40am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/4 "2017-09-15T04:40:16Z")

</div>

Yes, I need to mutate the array overtime. That’s why `sort!` is not so useful.  
I need to frequently run `a[k]` to find the value of k-th smallest integer and `find(a, v)` to find the rank of a particular value in the array. Therefore I want to have an efficiency in insertion and lookup.

---

<div class="post-metadata">

**Author:** ![raff](https://avatars.discourse-cdn.com/v4/letter/r/5e9695/32.png) [@raff](https://discourse.julialang.org/u/raff)\
**Post date:** [September 15, 2017, 4:50am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/5 "2017-09-15T04:50:47Z")

</div>

I tried SortedSet, but it doesn’t seem to have an easy way to run `a[k]` (to find the value of k-th smallest integer) and `find(a, v)` (to find the rank of a particular value in the array)  
Running `find(a, v)` results in the following:

```julia
julia> find(s, 4)
DataStructures.Tokens.IntSemiToken(4)

```

I expected to get the rank of it in the array (2).

Running `collect` each time before `find` doesn’t seem to be a good idea.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 15, 2017, 4:58am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/6 "2017-09-15T04:58:26Z")

</div>

Yup. It’s a set, so it’s not indexable.

---

<div class="post-metadata">

**Author:** ![dfdx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dfdx/32/120_2.png) [@dfdx](https://discourse.julialang.org/u/dfdx)\
**Post date:** [September 15, 2017, 8:28am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/7 "2017-09-15T08:28:10Z")

</div>

> [@raff](#):
>
> I need to frequently run a[k] to find the value of k-th smallest integer and find(a, v) to find the rank of a particular value in the array.

This sound like you need fast random access and lookup, but not insertion.

If so and you have relatively little insertions, ordinary arrays should work fine: just insert a new value into appropriate position and use `a[k]` and `find(a, v)` as is.

If insertion is relatively frequent, you may use an array of arrays (i.e. `Vector{Vector{T}}`) to mitigate insertion cost by inserting into smaller array. I don’t think there’s something ready-to-use, but it should be pretty easy to implement.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 15, 2017, 8:52am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/8 "2017-09-15T08:52:50Z")

</div>

Alternatively, `DataStructures.jl` has an internal implementation of balanced trees. Given that the `Sorted*` datastructures use it, it should be pretty well tested, and could serve as the basis for an implementation for `SortedArray`.

Which datastructure is best depends a lot on the relative frequency of insertions and lookups. Also, depending on problem sizes, constant factors may dominate asymptotic performance considerations. I would just start @dfdx’s suggestion and go from there.

Moreover, if you can put a bound on `k` _ex ante_, you can just use an array big enough for that.

---

<div class="post-metadata">

**Author:** ![raff](https://avatars.discourse-cdn.com/v4/letter/r/5e9695/32.png) [@raff](https://discourse.julialang.org/u/raff)\
**Post date:** [September 15, 2017, 12:58pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/9 "2017-09-15T12:58:31Z")

</div>

Thanks for the suggestions.  
The frequency of random access and lookup are roughly 2x-3x the frequency of insertion. The size of problem is roughly about a thousand item, so roughly 1000x insertion, 2000-3000x random access and lookup.

What is the complexity of `insert!(s, i, val)` function in Julia’s standard array? I could not find the information in the docs.

---

<div class="post-metadata">

**Author:** ![garrison](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/garrison/32/209519_2.png) [@garrison](https://discourse.julialang.org/u/garrison)\
**Post date:** [September 15, 2017, 6:39pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/10 "2017-09-15T18:39:13Z")

</div>

`insert!(s, i, val)` on a `Vector` is an `O(n)` operation because all elements are stored contiguously in memory, and all elements with index `i` or higher must be displaced to make room for the inserted element.

Also, instead of `find` (which performs linear search, taking `O(n)` time), you may wish to use `Base.Sort.searchsorted` (which performs binary search, taking `O(log(n))` time).

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [September 15, 2017, 7:39pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/11 "2017-09-15T19:39:31Z")

</div>

I have an open pull request at DataStructures.jl for a SortedVector type. You might want to try it out.

---

<div class="post-metadata">

**Author:** ![kevin.squire](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kevin.squire/32/62_2.png) [@kevin.squire](https://discourse.julialang.org/u/kevin.squire)\
**Post date:** [September 15, 2017, 10:53pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/12 "2017-09-15T22:53:24Z")

</div>

> [@garrison](#):
>
> insert!(s, i, val) on a Vector is an O(n) operation because all elements are stored contiguously in memory, and all elements with index i or higher must be displaced to make room for the inserted element.

Slight correction: Julia arrays grow at both the beginning and the end, so (after the first growth at the beginning), `insert!()` will choose the smaller amount of items to move.

Cheers!  
Kevin

---

<div class="post-metadata">

**Author:** ![Stephen\_Vavasis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephen_vavasis/32/3389_2.png) [@Stephen\_Vavasis](https://discourse.julialang.org/u/Stephen_Vavasis)\
**Post date:** [September 16, 2017, 3:39am UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/13 "2017-09-16T03:39:51Z")

</div>

If you want to invest time and effort into this project, you can augment the underlying balanced tree data structure that is used by SortedSet so that each internal tree node contains one additional field, namely, the number of leaves that descend from that node. The insertion and deletion operations on the balanced tree follow a path from a leaf to the root, and the new field can be modified appropriately on the internal tree nodes encountered during the traversal of this path. With this additional field, the kth largest element can be found in O(log n) operations, and the rank of an arbitrary element can also be found in O(log n) operations, where n is the total number of entries in the set. You would need to have a detailed understanding of the operations on a 2-3 tree and how the code implements them.

---

<div class="post-metadata">

**Author:** ![garrison](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/garrison/32/209519_2.png) [@garrison](https://discourse.julialang.org/u/garrison)\
**Post date:** [September 16, 2017, 3:11pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/14 "2017-09-16T15:11:16Z")

</div>

Wow, what a pleasant surprise; I did not realize that a `Vector` is really an array deque! In the past, I’ve always stored a vector in reverse if I planned to grow it (only) from the beginning, but now I know this to be unnecessary. I think this is something to emphasize in the documentation, somewhere.

---

<div class="post-metadata">

**Author:** ![colintbowers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/colintbowers/32/8033_2.png) [@colintbowers](https://discourse.julialang.org/u/colintbowers)\
**Post date:** [September 17, 2017, 11:54pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/15 "2017-09-17T23:54:41Z")

</div>

I actually did something like this as a sort-of “learn Julia” project. I haven’t looked at it in a few years, but the github repo is [here](https://github.com/colintbowers/SortedVectors.jl/blob/master/src/SortedVectors.jl). From memory, it has an immutable for `SortedVector` and `SortedUniqueVector`, and some functions from `Base`, like the deques, `intersect`, `union`, e.t.c. have methods for these types that exploit the sort order in the algorithm used.

Fair warning though: I was learning Julia at the time, so the code contains a lot of unnecessary functions. For example, I extended `Base.getindex` for lots of different input types, all of which could probably be reduced to one line.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [September 22, 2017, 12:42pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/16 "2017-09-22T12:42:57Z")

</div>

Maybe a sorted array isn’t best (trees with array-like properties may help):

**Streaming Cache-Oblivious B-Trees**  
[http://publications.csail.mit.edu/abstracts/abstracts07/jfineman/jfineman.html](http://publications.csail.mit.edu/abstracts/abstracts07/jfineman/jfineman.html)

> The **_shuttle tree_** , our main result, retains the same asymptotic search cost of the cache-oblivious B-tree while improving the insert cost.  
> […]  
> We give another data structure that we call a **_lookahead array_**. The lookahead array is reminiscent of static-to-dynamic transformations [7] and fractional cascading [11]. […] then the lookahead array is cache-oblivious and matches the performance of the BRT. We call this version the **_cache-oblivious lookahead array (COLA)_**.  
> […]  
> We next show how efficiently the COLA performs. We implemented a COLA and compared it with a B-tree. For databases in external memory, the COLA was 90 times faster than the B-tree for random inserts, 2.5 times slower for sorted inserts, and 1.7 times slower for searches.

See also (where I found the above): [https://www.quora.com/What-are-some-data-structures-that-can-maintain-a-sorted-list-allow-insertion-and-deletion-in-sub-linear-time-and-allow-iteration-through-the-list-as-quickly-as-possible](https://www.quora.com/What-are-some-data-structures-that-can-maintain-a-sorted-list-allow-insertion-and-deletion-in-sub-linear-time-and-allow-iteration-through-the-list-as-quickly-as-possible)

I’m not sure if the above is patented, but this one is, from memory… and seems similar):

> **[Fractal tree index](https://en.wikipedia.org/wiki/Fractal_tree_index)**
>
> In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. Like a B-tree, a fractal tree index is a generalization of a binary search tree in that a node can have more than two children. Furthermore, unlike a B-tree, a fractal tree index has buffers at each node, which allow insertions, deletions and other changes ...

I’m not sure if a [Kinetic sorted list - Wikipedia](https://en.wikipedia.org/wiki/Kinetic_sorted_list) helps you (directly) and this paper:

[http://www.sciencedirect.com/science/article/pii/S092577210600068X?via%3Dihub](http://www.sciencedirect.com/science/article/pii/S092577210600068X?via%3Dihub)

---

<div class="post-metadata">

**Author:** ![foobar\_lv](https://avatars.discourse-cdn.com/v4/letter/f/35a633/32.png) [@foobar\_lv](https://discourse.julialang.org/u/foobar_lv)\
**Post date:** [September 22, 2017, 2:47pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/17 "2017-09-22T14:47:15Z")

</div>

> Wow, what a pleasant surprise; I did not realize that a Vector is really an array deque!

Not quite! Adding elements to the left is still quite slow, as by default there is no space left at the beginning. After you removed some elements from the start it becomes fast, though.

As far as I know there is no “direct” (non pointer-manipulating) way of allocating space at the start of the Vector, i.e. of setting the offset in the corresponding C struct.

A way that kinda works is to allocate your array, and then deteteat! a part of the beginning, and then deleteat! the rest. Now you have an adequately sized array, which has quite a bit of room to grow at the start. However, the room at the start is hard limited so ~half of the array capacity (need to look up the array.c); if you exceed this limit, julia will memmove your data to the left and steal your offset.

This looks ugly but should actually have no overhead if you put bitstype content into your array. If you want to fill your array with object references, then you might pay a spurious memset, because julia needs to initialize all the object references to C\_NULL (“undef” in julia parlance).

I am not entirely sure whether the offset will be preserved if the array needs to be moved because you grow beyond the capacity; one would need to look this up in array.c.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [September 22, 2017, 3:00pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/18 "2017-09-22T15:00:01Z")

</div>

> [@foobar\_lv](#):
>
> Not quite! Adding elements to the left is still quite slow, as by default there is no space left at the beginning. After you removed some elements from the start it becomes fast, though.

Adding elements to the left will also reserve space.

---

<div class="post-metadata">

**Author:** ![raff](https://avatars.discourse-cdn.com/v4/letter/r/5e9695/32.png) [@raff](https://discourse.julialang.org/u/raff)\
**Post date:** [September 22, 2017, 3:22pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/19 "2017-09-22T15:22:30Z")

</div>

Thank you for all comments and suggestions. It’s really helpful.  
I just found that I can modify my algorithm so that it does not require SortedArray.  
It has been a great discussion though.

---

<div class="post-metadata">

**Author:** ![foobar\_lv](https://avatars.discourse-cdn.com/v4/letter/f/35a633/32.png) [@foobar\_lv](https://discourse.julialang.org/u/foobar_lv)\
**Post date:** [September 22, 2017, 3:22pm UTC](https://discourse.julialang.org/t/sorted-array-implementation/5897/20 "2017-09-22T15:22:57Z")

</div>

I find myself in the same situation; I need to operate in-place on very sparse vectors, and cannot use hashmaps because I need to find pivots.

Julia sparse vectors are useless for this task as inserting an element into an N-element vector costs O(N) instead of O(log N).

A pretty fast library and algorithm is judy ([Judy array - Wikipedia](https://en.wikipedia.org/wiki/Judy_array)), available on almost all linux distros. Judy is radix-based, so you cannot use your own comparison function.

Unfortunately there is no current public julia wrapper for the absolutely atrocious C api of judylib. There is a currently defunct JudyDict package. Starting from there, I wrote my own paper-thin low-quality segfault-on-mistake wrapper (you want to start from JudyDict because “man judy” is kinda ambiguous about the API and the judy source code is unreadable).

Most Judy implementations don’t directly allow arbitrary length keys (they take UInt64 or C strings, but the latter get Null-terminated). This is rather unfortunate, since I would be very very happy if I could plug in longer keys; however, I am loathe to touch any judy code with a 10 foot pole.

When considering speed comparisons between Judy and hash-tables, you will see that judy is almost competitive, but slightly slower. On the other hand, for our applications (range queries! Nth element by sort order! Privot!) hash tables just don’t cut the cake, and judy will beat every red-black-tree, as long as your array/tree fits into main memory.

In your case, you want a sorted dict with Key::Int64, Value::Bool. There is Judy1 available for this usecase. You will see that judy automatically compresses common prefixes from your keys; e.g. your Int64s which might mostly share 4 zero bytes at the start are almost as fast and memory efficient as proper Int32s (which is nice because my distro’s judylib does not support Int32 keys). Common postfixes are not compressed, so don’t left-shift your ints.

Unfortunately, judyset does not support deletion of ranges, even though it “should” be simple to implement. Alas, nothing about judy is “simple”; hence I will refrain from trying to implement range-delete until I absolutely need it.

[Next page](https://discourse.julialang.org/t/sorted-array-implementation/5897.md?page=2)