# Custom data structure for repeatedly partial sorting constant-size array

**URL:** <https://discourse.julialang.org/t/custom-data-structure-for-repeatedly-partial-sorting-constant-size-array/107594>\
**Category:** Performance\
**Tags:** sort\
**Created:** [December 14, 2023, 1:45am UTC](https://discourse.julialang.org/t/custom-data-structure-for-repeatedly-partial-sorting-constant-size-array/107594 "2023-12-14T01:45:45Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![jacob-roth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jacob-roth/32/1862_2.png) [@jacob-roth](https://discourse.julialang.org/u/jacob-roth)\
**Post date:** [December 14, 2023, 1:45am UTC](https://discourse.julialang.org/t/custom-data-structure-for-repeatedly-partial-sorting-constant-size-array/107594/1 "2023-12-14T01:45:45Z")

</div>

I have an application where, as a subroutine, I need to (partial) sort a specific n-dimensional vector repeatedly (for n\>10^7). Given initial data x^{(0)} and some perturbation \epsilon^{(i)} in step i, I want to obtain x^{(i)} = \texttt{sort}(x^{(i-1)} + \epsilon^{(i)}) and the permutation \pi such that (x^{(i-1)} + \epsilon^{(i)})\_\pi = x^{(i)}.

So, I am repeatedly (partial) sorting a vector of the same dimension. Based on the discussion [here](https://discourse.julialang.org/t/faster-alternatives-to-sortperm/80170/7), it was suggested to use a custom data structure. What I have done so far is to pre-allocate `x = zeros(Float64, n)`, `e = zeros(Float64, n)`, and `p = zeros(Int64, n)` and then call `sortperm!` (or `partialsortperm!`) on my data in step `i`. Is there a data structure that I could use in this case to speed up the `sortperm!`?

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [December 14, 2023, 2:10am UTC](https://discourse.julialang.org/t/custom-data-structure-for-repeatedly-partial-sorting-constant-size-array/107594/2 "2023-12-14T02:10:35Z")

</div>

Not a direct reply, but you can find such specific datatypes for example in [DataStructures.jl](https://juliacollections.github.io/DataStructures.jl/latest/), see the [Sorted Containers](https://juliacollections.github.io/DataStructures.jl/latest/sorted_containers/) section.

However, my feeling is that these types can only help if the perturbation \epsilon^{(i)} is sparse, e.g. if you can somehow replace the addition with a few `delete!` and `push!` operations.