Sorting algorithms: partial quicksort usage

question

#1

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> 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 http://en.cppreference.com/w/cpp/algorithm/partial_sort partial_sort.


#2

Julia’s sort-implementation uses InsertionSort if the argument has less than 22 elements, no matter what algorithm you specify (see e.g. here):

julia> arr = rand(22);

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