# Package for partial sorting output iterator

**URL:** <https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408>\
**Category:** General Usage\
**Tags:** question, sort\
**Created:** [July 2, 2025, 12:58pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408 "2025-07-02T12:58:49Z")\
**Posts on this page:** 8\
**Page:** 1

<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:** [July 2, 2025, 12:58pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/1 "2025-07-02T12:58:49Z")

</div>

Is there an implementation that partial sorts an iterator without allocating the whole output?

Eg suppose that I need the `n` largest elements by `f` from an iterator `itr` that has N \gg n elements.

`partialsort!(collect(itr), n; by f)` would allocate a length `N` vector, while the whole thing can be handled with a length `n` vector that is kept sorted.

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [July 2, 2025, 1:46pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/2 "2025-07-02T13:46:11Z")

</div>

One quick implementation would be like:

```julia
using DataStructures
function partialsort(itr, n)
    ret = SortedSet{eltype(itr)}()
    for x in itr
        push!(ret, x)
        if length(ret) > n
            pop!(ret)
        end
    end
    ret
end

```

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [July 2, 2025, 2:27pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/3 "2025-07-02T14:27:43Z")

</div>

Perhaps `SortedSet` can cause problems because it folds identical items (as a mathematical set does). An alternative data structure to use is a heap:

```julia
function partialsort2(itr, n)
    ret = BinaryMinMaxHeap{eltype(itr)}()
    for x in itr
        push!(ret, x)
        if length(ret) > n
            popmin!(ret)
        end
    end
    ret
end

```

---

<div class="post-metadata">

**Author:** ![abraunst](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraunst/32/6880_2.png) [@abraunst](https://discourse.julialang.org/u/abraunst)\
**Post date:** [July 9, 2025, 12:03pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/4 "2025-07-09T12:03:54Z")

</div>

Note that these two solutions are O(N\log n) while `partialsort!` has the potential to be O(N) (I didn’t look at the actual implementation though).

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [July 9, 2025, 12:45pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/5 "2025-07-09T12:45:06Z")

</div>

You can’t do better than `O(N log(N))` for full [comparison sort](https://en.wikipedia.org/wiki/Comparison_sort). This means in general you also can’t to partial sort in `O(N)`. Otherwise you would just choose `n=N` and end up with a faster full comparison sort.  
Now if your problem has extra structure, there can be faster algorithms. Like `O(N)` radix sort for a vector of integers. Or `O(1)` if your collection is say a range.

---

<div class="post-metadata">

**Author:** ![abraunst](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraunst/32/6880_2.png) [@abraunst](https://discourse.julialang.org/u/abraunst)\
**Post date:** [July 9, 2025, 1:04pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/6 "2025-07-09T13:04:17Z")

</div>

I think you are misinterpreting `partialsort!`. You don’t need the output array to be sorted, you only need to find the position of the `n`-th smallest element (and as a consequence you can find the position of the `n` smallest elements with an extra `O(n)` time). Setting `n=N` would just give you the largest element, which obviously can be found in time `O(N)`.

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [July 9, 2025, 1:19pm UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/7 "2025-07-09T13:19:52Z")

</div>

Oh thanks for clarifying.

---

<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:** [July 10, 2025, 1:14am UTC](https://discourse.julialang.org/t/package-for-partial-sorting-output-iterator/130408/8 "2025-07-10T01:14:48Z")

</div>

I think this operation may done in O(N) time as follows. For simplicity of explanation, assume N is a multiple of n. Form a buffer with 2n slots. Initially load the buffer with 2n items from the iterator. Then find the median, which requires O(n) time, and discard the elements below the median, leaving n items in the buffer. Now load another n items from the iterator, again filling the buffer. Repeat the operation of taking the median and discarding the n smaller elements. The number of median operations is N/n, and each one requires O(n) operations, so the total running time is O(N).

The OP asked for a package rather than an algorithm; I don’t know of a package to implement this operation.