# Sorting algorithms: partial quicksort usage

**URL:** <https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007>\
**Category:** General Usage\
**Tags:** question, sort\
**Created:** [December 17, 2016, 4:04pm UTC](https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007 "2016-12-17T16:04:12Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![jesse](https://avatars.discourse-cdn.com/v4/letter/j/c77e96/32.png) [@jesse](https://discourse.julialang.org/u/jesse)\
**Post date:** [December 17, 2016, 4:04pm UTC](https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007/1 "2016-12-17T16:04:12Z")

</div>

Hi,

Im trying to understand the partial quicksort algorithm. I expected it work so that if I specify `alg=PartialQuickSort(3)` the algorithm sorts so that indexes 1,2,3 contains the smallest elements and the rest (4,…,n) is in unspecified order. I just tried the algorithm and the results are the following:

```julia
julia> arr = rand(10)
10-element Array{Float64,1}:
 0.0771121
 0.375159 
 0.537209 
 0.0500928
 0.578713 
 0.156671 
 0.829953 
 0.552534 
 0.81353  
 0.804142 

julia> ps = sort(arr, alg=PartialQuickSort(3))
10-element Array{Float64,1}:
 0.0500928
 0.0771121
 0.156671 
 0.375159 
 0.537209 
 0.552534 
 0.578713 
 0.804142 
 0.81353  
 0.829953 

julia> sort(arr, alg=PartialQuickSort(3)) == sort(arr)
true

```

Which is a little weird? Or is it? I expected it work like c++ STL function [std::partial\_sort - cppreference.com](http://en.cppreference.com/w/cpp/algorithm/partial_sort) `partial_sort`.

---

<div class="post-metadata">

**Author:** ![pfitzseb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pfitzseb/32/45566_2.png) [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)\
**Post date:** [December 17, 2016, 4:46pm UTC](https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007/2 "2016-12-17T16:46:48Z")

</div>

Julia’s `sort`-implementation uses `InsertionSort` if the argument has less than 22 elements, no matter what algorithm you specify (see e.g. [here](https://github.com/JuliaLang/julia/blob/363ecad77577bb23621941b47df15ca3fb9f7775/base/sort.jl#L391)):

```julia
julia> arr = rand(22);

julia> sort(arr, alg=PartialQuickSort(3)) == sort(arr)
false

```

---

<div class="post-metadata">

**Author:** ![Noel\_Araujo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/noel_araujo/32/4862_2.png) [@Noel\_Araujo](https://discourse.julialang.org/u/Noel_Araujo)\
**Post date:** [March 16, 2019, 10:17pm UTC](https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007/3 "2019-03-16T22:17:22Z")

</div>

I’m stupid or something.  
But I cannot make this example to work, even for more than 22 elements

> x = rand(100)  
> xx = sort(x; alg=PartialQuickSort(50))

The final length of `xx` is 100, and not 50 🙁

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [March 16, 2019, 10:36pm UTC](https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007/4 "2019-03-16T22:36:33Z")

</div>

Did you see the first post?

> the algorithm sorts so that indexes 1,2,3 contains the smallest elements and the rest (4,…,n) is in unspecified order

Also see this section in the [manual](https://docs.julialang.org/en/latest/base/sort/#Sorting-Algorithms-1):

> the output array is only sorted up to index `k`

---

<div class="post-metadata">

**Author:** ![Noel\_Araujo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/noel_araujo/32/4862_2.png) [@Noel\_Araujo](https://discourse.julialang.org/u/Noel_Araujo)\
**Post date:** [March 16, 2019, 10:57pm UTC](https://discourse.julialang.org/t/sorting-algorithms-partial-quicksort-usage/1007/5 "2019-03-16T22:57:57Z")

</div>

ah…😃  
now I got it