# 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:** 2
**Page:** 1
### Author:  [@heliosdrm](https://discourse.julialang.org/u/heliosdrm)
#### Post date: [February 2, 2022, 2:17pm UTC](https://discourse.julialang.org/t/insert-value-into-sorted-array-with-fixed-size/75660/1 "2022-02-02T14:17:53Z")
I want to insert a value into a sorted array with fixed size, removing the last (greatest) value of the array. A naive solution is this function that combines `insert!` (or `pushfirst!`) and `pop!`:
```julia
function insertandropgreatest_naive!(collection, newvalue)
if newvalue >= last(collection)
return collection
end
i = searchsortedlast(collection, newvalue)
if i==0
pushfirst!(collection, newvalue)
else
insert!(collection, i, newvalue)
end
pop!(collection)
return collection
end
```
I thought that it would be better to make something that does not redimension the array, like this:
```julia
function insertandropgreatest_fixedsize!(collection, newvalue)
# do nothing if newvalue is greater than greatest in collection
if newvalue >= last(collection)
return collection
end
# search, and replace...
for i = length(collection):-1:2
collection[i] = collection[i-1]
if newvalue >= collection[i]
collection[i] = newvalue
return collection
end
end
# replace in first position if newvalue is smaller than smallest in collection
collection[1] = newvalue
return collection
end
```
An advantage of this is that it works with `MArrays` (from StaticArrays.jl), but for standard arrays I can’t see a big gain in performance. Is the “naive” version sufficiently optimized for this problem, or does anyone have some suggestion to improve it?
NB: I’m starting the search from the greatest to the smallest, because I expect `newvalue` to be greater than all elements of `collection` more frequently.
---
### Author:  [@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")
> [@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)