# Insert value into sorted array with fixed size

**URL:** https://discourse.julialang.org/t/insert-value-into-sorted-array-with-fixed-size/75660
**Category:** General Usage
**Tags:** performance, arrays
**Created:** [February 2, 2022, 2:17pm UTC](https://discourse.julialang.org/t/insert-value-into-sorted-array-with-fixed-size/75660 "2022-02-02T14:17:53Z")
**Posts on this page:** 1
**Showing post:** 2

<div class="post-metadata">

### Author: ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)
#### Post date: [February 2, 2022, 3:45pm UTC](https://discourse.julialang.org/t/insert-value-into-sorted-array-with-fixed-size/75660/2 "2022-02-02T15:45:03Z")

</div>

> [@heliosdrm](#):
>
> Is the “naive” version sufficiently optimized for this problem, or does anyone have some suggestion to improve it?

I think your idea to avoid resizing the array is sensible (although probably not a huge win), and being able to work with MArrays is a good idea too. However, your second option loses some benefit by doing a linear search over the entire collection, when that might not actually be necessary. It also has a branch inside the inner loop, which may interfere with your CPUs pipelining and branch prediction.

Perhaps you could instead do:

1. Use `searchsortedlast` to find the right place to put the value
2. Use `copyto!` (or a for loop) to shift the data after that index by one to make room.
3. Put the new value into the space you’ve just made

On the other hand, if you’re dealing with lots of sorted data, you might be better off using a different data structure entirely, like the ones from [Sorted Containers · DataStructures.jl](https://juliacollections.github.io/DataStructures.jl/v0.9/sorted_containers.html)

Alternatively, if your collections are small, there may be no advantage to using `searchsortedlast`, in which case your second option may actually be optimal.

Edit: But you can probably save some time using the usual `@inbounds` stuff from [Performance Tips · The Julia Language](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-annotations)

---

_[View the full topic](https://discourse.julialang.org/t/insert-value-into-sorted-array-with-fixed-size/75660)._