StatProfilerHTML.jl report
Generated on Thu, 26 Mar 2020 19:09:01
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 module Sort
4
5 import ..@__MODULE__, ..parentmodule
6 const Base = parentmodule(@__MODULE__)
7 using .Base.Order
8 using .Base: copymutable, LinearIndices, length, (:),
9 eachindex, axes, first, last, similar, zip, OrdinalRange,
10 AbstractVector, @inbounds, AbstractRange, @eval, @inline, Vector, @noinline,
11 AbstractMatrix, AbstractUnitRange, isless, identity, eltype, >, <, <=, >=, |, +, -, *, !,
12 extrema, sub_with_overflow, add_with_overflow, oneunit, div, getindex, setindex!,
13 length, resize!, fill, Missing, require_one_based_indexing
14
15 using .Base: >>>, !==
16
17 import .Base:
18 sort,
19 sort!,
20 issorted,
21 sortperm,
22 to_indices
23
24 export # also exported by Base
25 # order-only:
26 issorted,
27 searchsorted,
28 searchsortedfirst,
29 searchsortedlast,
30 # order & algorithm:
31 sort,
32 sort!,
33 sortperm,
34 sortperm!,
35 partialsort,
36 partialsort!,
37 partialsortperm,
38 partialsortperm!,
39 # algorithms:
40 InsertionSort,
41 QuickSort,
42 MergeSort,
43 PartialQuickSort
44
45 export # not exported by Base
46 Algorithm,
47 DEFAULT_UNSTABLE,
48 DEFAULT_STABLE,
49 SMALL_ALGORITHM,
50 SMALL_THRESHOLD
51
52
53 ## functions requiring only ordering ##
54
55 function issorted(itr, order::Ordering)
56 y = iterate(itr)
57 y === nothing && return true
58 prev, state = y
59 y = iterate(itr, state)
60 while y !== nothing
61 this, state = y
62 lt(order, this, prev) && return false
63 prev = this
64 y = iterate(itr, state)
65 end
66 return true
67 end
68
69 """
70 issorted(v, lt=isless, by=identity, rev:Bool=false, order::Ordering=Forward)
71
72 Test whether a vector is in sorted order. The `lt`, `by` and `rev` keywords modify what
73 order is considered to be sorted just as they do for [`sort`](@ref).
74
75 # Examples
76 ```jldoctest
77 julia> issorted([1, 2, 3])
78 true
79
80 julia> issorted([(1, "b"), (2, "a")], by = x -> x[1])
81 true
82
83 julia> issorted([(1, "b"), (2, "a")], by = x -> x[2])
84 false
85
86 julia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true)
87 true
88 ```
89 """
90 issorted(itr;
91 lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
92 issorted(itr, ord(lt,by,rev,order))
93
94 function partialsort!(v::AbstractVector, k::Union{Integer,OrdinalRange}, o::Ordering)
95 inds = axes(v, 1)
96 sort!(v, first(inds), last(inds), PartialQuickSort(k), o)
97 maybeview(v, k)
98 end
99
100 maybeview(v, k) = view(v, k)
101 maybeview(v, k::Integer) = v[k]
102
103 """
104 partialsort!(v, k; by=<transform>, lt=<comparison>, rev=false)
105
106 Partially sort the vector `v` in place, according to the order specified by `by`, `lt` and
107 `rev` so that the value at index `k` (or range of adjacent values if `k` is a range) occurs
108 at the position where it would appear if the array were fully sorted via a non-stable
109 algorithm. If `k` is a single index, that value is returned; if `k` is a range, an array of
110 values at those indices is returned. Note that `partialsort!` does not fully sort the input
111 array.
112
113 # Examples
114 ```jldoctest
115 julia> a = [1, 2, 4, 3, 4]
116 5-element Array{Int64,1}:
117 1
118 2
119 4
120 3
121 4
122
123 julia> partialsort!(a, 4)
124 4
125
126 julia> a
127 5-element Array{Int64,1}:
128 1
129 2
130 3
131 4
132 4
133
134 julia> a = [1, 2, 4, 3, 4]
135 5-element Array{Int64,1}:
136 1
137 2
138 4
139 3
140 4
141
142 julia> partialsort!(a, 4, rev=true)
143 2
144
145 julia> a
146 5-element Array{Int64,1}:
147 4
148 4
149 3
150 2
151 1
152 ```
153 """
154 partialsort!(v::AbstractVector, k::Union{Integer,OrdinalRange};
155 lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
156 partialsort!(v, k, ord(lt,by,rev,order))
157
158 """
159 partialsort(v, k, by=<transform>, lt=<comparison>, rev=false)
160
161 Variant of [`partialsort!`](@ref) which copies `v` before partially sorting it, thereby returning the
162 same thing as `partialsort!` but leaving `v` unmodified.
163 """
164 partialsort(v::AbstractVector, k::Union{Integer,OrdinalRange}; kws...) =
165 partialsort!(copymutable(v), k; kws...)
166
167 # This implementation of `midpoint` is performance-optimized but safe
168 # only if `lo <= hi`.
169 midpoint(lo::T, hi::T) where T<:Integer = lo + ((hi - lo) >>> 0x01)
170 midpoint(lo::Integer, hi::Integer) = midpoint(promote(lo, hi)...)
171
172 # reference on sorted binary search:
173 # http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary
174
175 # index of the first value of vector a that is greater than or equal to x;
176 # returns length(v)+1 if x is greater than all values in v.
177 function searchsortedfirst(v::AbstractVector, x, lo::T, hi::T, o::Ordering) where T<:Integer
178 u = T(1)
179 lo = lo - u
180 hi = hi + u
181 @inbounds while lo < hi - u
182 m = midpoint(lo, hi)
183 if lt(o, v[m], x)
184 lo = m
185 else
186 hi = m
187 end
188 end
189 return hi
190 end
191
192 # index of the last value of vector a that is less than or equal to x;
193 # returns 0 if x is less than all values of v.
194 function searchsortedlast(v::AbstractVector, x, lo::T, hi::T, o::Ordering) where T<:Integer
195 u = T(1)
196 lo = lo - u
197 hi = hi + u
198 @inbounds while lo < hi - u
199 m = midpoint(lo, hi)
200 if lt(o, x, v[m])
201 hi = m
202 else
203 lo = m
204 end
205 end
206 return lo
207 end
208
209 # returns the range of indices of v equal to x
210 # if v does not contain x, returns a 0-length range
211 # indicating the insertion point of x
212 function searchsorted(v::AbstractVector, x, ilo::T, ihi::T, o::Ordering) where T<:Integer
213 u = T(1)
214 lo = ilo - u
215 hi = ihi + u
216 @inbounds while lo < hi - u
217 m = midpoint(lo, hi)
218 if lt(o, v[m], x)
219 lo = m
220 elseif lt(o, x, v[m])
221 hi = m
222 else
223 a = searchsortedfirst(v, x, max(lo,ilo), m, o)
224 b = searchsortedlast(v, x, m, min(hi,ihi), o)
225 return a : b
226 end
227 end
228 return (lo + 1) : (hi - 1)
229 end
230
231 function searchsortedlast(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering)
232 require_one_based_indexing(a)
233 if step(a) == 0
234 lt(o, x, first(a)) ? 0 : length(a)
235 else
236 n = round(Integer, clamp((x - first(a)) / step(a) + 1, 1, length(a)))
237 lt(o, x, a[n]) ? n - 1 : n
238 end
239 end
240
241 function searchsortedfirst(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering)
242 require_one_based_indexing(a)
243 if step(a) == 0
244 lt(o, first(a), x) ? length(a) + 1 : 1
245 else
246 n = round(Integer, clamp((x - first(a)) / step(a) + 1, 1, length(a)))
247 lt(o, a[n] ,x) ? n + 1 : n
248 end
249 end
250
251 function searchsortedlast(a::AbstractRange{<:Integer}, x::Real, o::DirectOrdering)
252 require_one_based_indexing(a)
253 h = step(a)
254 if h == 0
255 lt(o, x, first(a)) ? 0 : length(a)
256 elseif h > 0 && x < first(a)
257 firstindex(a) - 1
258 elseif h > 0 && x >= last(a)
259 lastindex(a)
260 elseif h < 0 && x > first(a)
261 firstindex(a) - 1
262 elseif h < 0 && x <= last(a)
263 lastindex(a)
264 else
265 fld(floor(Integer, x) - first(a), h) + 1
266 end
267 end
268
269 function searchsortedfirst(a::AbstractRange{<:Integer}, x::Real, o::DirectOrdering)
270 require_one_based_indexing(a)
271 h = step(a)
272 if h == 0
273 lt(o, first(a), x) ? length(a)+1 : 1
274 elseif h > 0 && x <= first(a)
275 firstindex(a)
276 elseif h > 0 && x > last(a)
277 lastindex(a) + 1
278 elseif h < 0 && x >= first(a)
279 firstindex(a)
280 elseif h < 0 && x < last(a)
281 lastindex(a) + 1
282 else
283 -fld(floor(Integer, -x) + first(a), h) + 1
284 end
285 end
286
287 function searchsortedfirst(a::AbstractRange{<:Integer}, x::Unsigned, o::DirectOrdering)
288 require_one_based_indexing(a)
289 if lt(o, first(a), x)
290 if step(a) == 0
291 length(a) + 1
292 else
293 min(cld(x - first(a), step(a)), length(a)) + 1
294 end
295 else
296 1
297 end
298 end
299
300 function searchsortedlast(a::AbstractRange{<:Integer}, x::Unsigned, o::DirectOrdering)
301 require_one_based_indexing(a)
302 if lt(o, x, first(a))
303 0
304 elseif step(a) == 0
305 length(a)
306 else
307 min(fld(x - first(a), step(a)) + 1, length(a))
308 end
309 end
310
311 searchsorted(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering) =
312 searchsortedfirst(a, x, o) : searchsortedlast(a, x, o)
313
314 for s in [:searchsortedfirst, :searchsortedlast, :searchsorted]
315 @eval begin
316 $s(v::AbstractVector, x, o::Ordering) = (inds = axes(v, 1); $s(v,x,first(inds),last(inds),o))
317 $s(v::AbstractVector, x;
318 lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
319 $s(v,x,ord(lt,by,rev,order))
320 end
321 end
322
323 """
324 searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
325
326 Return the range of indices of `a` which compare as equal to `x` (using binary search)
327 according to the order specified by the `by`, `lt` and `rev` keywords, assuming that `a`
328 is already sorted in that order. Return an empty range located at the insertion point
329 if `a` does not contain values equal to `x`.
330
331 # Examples
332 ```jldoctest
333 julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
334 3:3
335
336 julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
337 4:5
338
339 julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
340 3:2
341
342 julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
343 7:6
344
345 julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
346 1:0
347 ```
348 """ searchsorted
349
350 """
351 searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false)
352
353 Return the index of the first value in `a` greater than or equal to `x`, according to the
354 specified order. Return `length(a) + 1` if `x` is greater than all values in `a`.
355 `a` is assumed to be sorted.
356
357 # Examples
358 ```jldoctest
359 julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match
360 3
361
362 julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches
363 4
364
365 julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
366 3
367
368 julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
369 7
370
371 julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
372 1
373 ```
374 """ searchsortedfirst
375
376 """
377 searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false)
378
379 Return the index of the last value in `a` less than or equal to `x`, according to the
380 specified order. Return `0` if `x` is less than all values in `a`. `a` is assumed to
381 be sorted.
382
383 # Examples
384 ```jldoctest
385 julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match
386 3
387
388 julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches
389 5
390
391 julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
392 2
393
394 julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
395 6
396
397 julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
398 0
399 ```
400 """ searchsortedlast
401
402
403 ## sorting algorithms ##
404
405 abstract type Algorithm end
406
407 struct InsertionSortAlg <: Algorithm end
408 struct QuickSortAlg <: Algorithm end
409 struct MergeSortAlg <: Algorithm end
410
411 """
412 PartialQuickSort{T <: Union{Integer,OrdinalRange}}
413
414 Indicate that a sorting function should use the partial quick sort
415 algorithm. Partial quick sort returns the smallest `k` elements sorted from smallest
416 to largest, finding them and sorting them using [`QuickSort`](@ref).
417
418 Characteristics:
419 * *not stable*: does not preserve the ordering of elements which
420 compare equal (e.g. "a" and "A" in a sort of letters which
421 ignores case).
422 * *in-place* in memory.
423 * *divide-and-conquer*: sort strategy similar to [`MergeSort`](@ref).
424 """
425 struct PartialQuickSort{T <: Union{Integer,OrdinalRange}} <: Algorithm
426 k::T
427 end
428
429
430 """
431 InsertionSort
432
433 Indicate that a sorting function should use the insertion sort
434 algorithm. Insertion sort traverses the collection one element
435 at a time, inserting each element into its correct, sorted position in
436 the output list.
437
438 Characteristics:
439 * *stable*: preserves the ordering of elements which
440 compare equal (e.g. "a" and "A" in a sort of letters
441 which ignores case).
442 * *in-place* in memory.
443 * *quadratic performance* in the number of elements to be sorted:
444 it is well-suited to small collections but should not be used for large ones.
445 """
446 const InsertionSort = InsertionSortAlg()
447 """
448 QuickSort
449
450 Indicate that a sorting function should use the quick sort
451 algorithm, which is *not* stable.
452
453 Characteristics:
454 * *not stable*: does not preserve the ordering of elements which
455 compare equal (e.g. "a" and "A" in a sort of letters which
456 ignores case).
457 * *in-place* in memory.
458 * *divide-and-conquer*: sort strategy similar to [`MergeSort`](@ref).
459 * *good performance* for large collections.
460 """
461 const QuickSort = QuickSortAlg()
462 """
463 MergeSort
464
465 Indicate that a sorting function should use the merge sort
466 algorithm. Merge sort divides the collection into
467 subcollections and repeatedly merges them, sorting each
468 subcollection at each step, until the entire
469 collection has been recombined in sorted form.
470
471 Characteristics:
472 * *stable*: preserves the ordering of elements which compare
473 equal (e.g. "a" and "A" in a sort of letters which ignores
474 case).
475 * *not in-place* in memory.
476 * *divide-and-conquer* sort strategy.
477 """
478 const MergeSort = MergeSortAlg()
479
480 const DEFAULT_UNSTABLE = QuickSort
481 const DEFAULT_STABLE = MergeSort
482 const SMALL_ALGORITHM = InsertionSort
483 const SMALL_THRESHOLD = 20
484
485
28 (3 %) samples spent in sort!
6 (21 %) (ex.), 28 (100 %) (incl.) when called from sort! line 575
function sort!(v::AbstractVector, lo::Integer, hi::Integer, ::InsertionSortAlg, o::Ordering)
486 @inbounds for i = lo+1:hi
487 j = i
488 10 (1 %)
10 (100 %) samples spent calling getindex
x = v[i]
489 while j > lo
490 11 (1 %)
1 (9 %) samples spent calling getindex
10 (91 %) samples spent calling lt
if lt(o, x, v[j-1])
491 1 (0 %)
1 (100 %) samples spent calling getindex
v[j] = v[j-1]
492 j -= 1
493 continue
494 end
495 break
496 end
497 4 (0 %) 4 (0 %) v[j] = x
498 end
499 2 (0 %) 2 (0 %) return v
500 end
501
502 # selectpivot!
503 #
504 # Given 3 locations in an array (lo, mi, and hi), sort v[lo], v[mi], v[hi]) and
505 # choose the middle value as a pivot
506 #
507 # Upon return, the pivot is in v[lo], and v[hi] is guaranteed to be
508 # greater than the pivot
509
510 @inline function selectpivot!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
511 @inbounds begin
512 mi = midpoint(lo, hi)
513
514 # sort v[mi] <= v[lo] <= v[hi] such that the pivot is immediately in place
515 if lt(o, v[lo], v[mi])
516 v[mi], v[lo] = v[lo], v[mi]
517 end
518
519 if lt(o, v[hi], v[lo])
520 if lt(o, v[hi], v[mi])
521 v[hi], v[lo], v[mi] = v[lo], v[mi], v[hi]
522 else
523 v[hi], v[lo] = v[lo], v[hi]
524 end
525 end
526
527 # return the pivot
528 return v[lo]
529 end
530 end
531
532 # partition!
533 #
534 # select a pivot, and partition v according to the pivot
535
536 function partition!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
537 pivot = selectpivot!(v, lo, hi, o)
538 # pivot == v[lo], v[hi] > pivot
539 i, j = lo, hi
540 @inbounds while true
541 i += 1; j -= 1
542 while lt(o, v[i], pivot); i += 1; end;
543 while lt(o, pivot, v[j]); j -= 1; end;
544 i >= j && break
545 v[i], v[j] = v[j], v[i]
546 end
547 v[j], v[lo] = pivot, v[j]
548
549 # v[j] == pivot
550 # v[k] >= pivot for k > j
551 # v[i] <= pivot for i < j
552 return j
553 end
554
555 function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::QuickSortAlg, o::Ordering)
556 @inbounds while lo < hi
557 hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
558 j = partition!(v, lo, hi, o)
559 if j-lo < hi-j
560 # recurse on the smaller chunk
561 # this is necessary to preserve O(log(n))
562 # stack space in the worst case (rather than O(n))
563 lo < (j-1) && sort!(v, lo, j-1, a, o)
564 lo = j+1
565 else
566 j+1 < hi && sort!(v, j+1, hi, a, o)
567 hi = j-1
568 end
569 end
570 return v
571 end
572
573
4393 (527 %) samples spent in sort!
7 (0 %) (ex.), 1880 (43 %) (incl.) when called from sort! line 581
3 (0 %) (ex.), 1911 (44 %) (incl.) when called from sort! line 580
1 (0 %) (ex.), 602 (14 %) (incl.) when called from sort! line 574
function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::MergeSortAlg, o::Ordering, t=similar(v,0))
574 602 (72 %)
602 (72 %) samples spent in sort!
602 (100 %) (incl.) when called from sort! line 665
602 (100 %) samples spent calling sort!
@inbounds if lo < hi
575 1 (0 %) 29 (3 %)
28 (100 %) samples spent calling sort!
hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
576
577 m = midpoint(lo, hi)
578 (length(t) < m-lo+1) && resize!(t, m-lo+1)
579
580 1911 (229 %)
1911 (100 %) samples spent calling sort!
sort!(v, lo, m, a, o, t)
581 1880 (225 %)
1880 (100 %) samples spent calling sort!
sort!(v, m+1, hi, a, o, t)
582
583 i, j = 1, lo
584 1 (0 %)
1 (100 %) samples spent calling <=
while j <= m
585 71 (9 %)
68 (96 %) samples spent calling setindex!
3 (4 %) samples spent calling getindex
t[i] = v[j]
586 i += 1
587 9 (1 %)
9 (100 %) samples spent calling +
j += 1
588 end
589
590 i, k = 1, lo
591 11 (1 %) 11 (1 %) while k < j <= hi
592 373 (45 %)
34 (9 %) samples spent calling getindex
1 (0 %) samples spent calling getindex
338 (91 %) samples spent calling lt
if lt(o, v[j], t[i])
593 25 (3 %)
25 (100 %) samples spent calling setindex!
v[k] = v[j]
594 26 (3 %)
26 (100 %) samples spent calling +
j += 1
595 else
596 23 (3 %)
23 (100 %) samples spent calling setindex!
v[k] = t[i]
597 25 (3 %)
25 (100 %) samples spent calling +
i += 1
598 end
599 10 (1 %)
10 (100 %) samples spent calling +
k += 1
600 end
601 while k < j
602 v[k] = t[i]
603 k += 1
604 i += 1
605 end
606 end
607
608 return v
609 end
610
611 function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::PartialQuickSort{<:Integer},
612 o::Ordering)
613 @inbounds while lo < hi
614 hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
615 j = partition!(v, lo, hi, o)
616 if j >= a.k
617 # we don't need to sort anything bigger than j
618 hi = j-1
619 elseif j-lo < hi-j
620 # recurse on the smaller chunk
621 # this is necessary to preserve O(log(n))
622 # stack space in the worst case (rather than O(n))
623 lo < (j-1) && sort!(v, lo, j-1, a, o)
624 lo = j+1
625 else
626 (j+1) < hi && sort!(v, j+1, hi, a, o)
627 hi = j-1
628 end
629 end
630 return v
631 end
632
633
634 function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::PartialQuickSort{T},
635 o::Ordering) where T<:OrdinalRange
636 @inbounds while lo < hi
637 hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
638 j = partition!(v, lo, hi, o)
639
640 if j <= first(a.k)
641 lo = j+1
642 elseif j >= last(a.k)
643 hi = j-1
644 else
645 if j-lo < hi-j
646 lo < (j-1) && sort!(v, lo, j-1, a, o)
647 lo = j+1
648 else
649 hi > (j+1) && sort!(v, j+1, hi, a, o)
650 hi = j-1
651 end
652 end
653 end
654 return v
655 end
656
657
658 ## generic sorting methods ##
659
660 defalg(v::AbstractArray) = DEFAULT_STABLE
661 defalg(v::AbstractArray{<:Union{Number, Missing}}) = DEFAULT_UNSTABLE
662
663 function sort!(v::AbstractVector, alg::Algorithm, order::Ordering)
664 inds = axes(v,1)
665 602 (72 %)
602 (72 %) samples spent in sort!
602 (100 %) (incl.) when called from #sort!#7 line 725
602 (100 %) samples spent calling sort!
sort!(v,first(inds),last(inds),alg,order)
666 end
667
668 """
669 sort!(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
670
671 Sort the vector `v` in place. [`QuickSort`](@ref) is used by default for numeric arrays while
672 [`MergeSort`](@ref) is used for other arrays. You can specify an algorithm to use via the `alg`
673 keyword (see [Sorting Algorithms](@ref) for available algorithms). The `by` keyword lets you provide
674 a function that will be applied to each element before comparison; the `lt` keyword allows
675 providing a custom "less than" function; use `rev=true` to reverse the sorting order. These
676 options are independent and can be used together in all possible combinations: if both `by`
677 and `lt` are specified, the `lt` function is applied to the result of the `by` function;
678 `rev=true` reverses whatever ordering specified via the `by` and `lt` keywords.
679
680 # Examples
681 ```jldoctest
682 julia> v = [3, 1, 2]; sort!(v); v
683 3-element Array{Int64,1}:
684 1
685 2
686 3
687
688 julia> v = [3, 1, 2]; sort!(v, rev = true); v
689 3-element Array{Int64,1}:
690 3
691 2
692 1
693
694 julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
695 3-element Array{Tuple{Int64,String},1}:
696 (1, "c")
697 (2, "b")
698 (3, "a")
699
700 julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
701 3-element Array{Tuple{Int64,String},1}:
702 (3, "a")
703 (2, "b")
704 (1, "c")
705 ```
706 """
707 function sort!(v::AbstractVector;
708 alg::Algorithm=defalg(v),
709 lt=isless,
710 by=identity,
711 rev::Union{Bool,Nothing}=nothing,
712 order::Ordering=Forward)
713 602 (72 %)
602 (72 %) samples spent in sort!##kw
602 (100 %) (incl.) when called from polynomial! line 72
602 (100 %) samples spent calling #sort!#7
ordr = ord(lt,by,rev,order)
714 if (ordr === Forward || ordr === Reverse) && eltype(v)<:Integer
715 n = length(v)
716 if n > 1
717 min, max = extrema(v)
718 (diff, o1) = sub_with_overflow(max, min)
719 (rangelen, o2) = add_with_overflow(diff, oneunit(diff))
720 if !o1 && !o2 && rangelen < div(n,2)
721 return sort_int_range!(v, rangelen, min, ordr === Reverse ? reverse : identity)
722 end
723 end
724 end
725 602 (72 %)
602 (72 %) samples spent in #sort!#7
602 (100 %) (incl.) when called from sort!##kw line 713
602 (100 %) samples spent calling sort!
sort!(v, alg, ordr)
726 end
727
728 # sort! for vectors of few unique integers
729 function sort_int_range!(x::AbstractVector{<:Integer}, rangelen, minval, maybereverse)
730 offs = 1 - minval
731
732 where = fill(0, rangelen)
733 @inbounds for i = eachindex(x)
734 where[x[i] + offs] += 1
735 end
736
737 idx = firstindex(x)
738 @inbounds for i = maybereverse(1:rangelen)
739 lastidx = idx + where[i] - 1
740 val = i-offs
741 for j = idx:lastidx
742 x[j] = val
743 end
744 idx = lastidx + 1
745 end
746
747 return x
748 end
749
750 """
751 sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
752
753 Variant of [`sort!`](@ref) that returns a sorted copy of `v` leaving `v` itself unmodified.
754
755 # Examples
756 ```jldoctest
757 julia> v = [3, 1, 2];
758
759 julia> sort(v)
760 3-element Array{Int64,1}:
761 1
762 2
763 3
764
765 julia> v
766 3-element Array{Int64,1}:
767 3
768 1
769 2
770 ```
771 """
772 sort(v::AbstractVector; kws...) = sort!(copymutable(v); kws...)
773
774 ## partialsortperm: the permutation to sort the first k elements of an array ##
775
776 """
777 partialsortperm(v, k; by=<transform>, lt=<comparison>, rev=false)
778
779 Return a partial permutation `I` of the vector `v`, so that `v[I]` returns values of a fully
780 sorted version of `v` at index `k`. If `k` is a range, a vector of indices is returned; if
781 `k` is an integer, a single index is returned. The order is specified using the same
782 keywords as `sort!`. The permutation is stable, meaning that indices of equal elements
783 appear in ascending order.
784
785 Note that this function is equivalent to, but more efficient than, calling `sortperm(...)[k]`.
786
787 # Examples
788 ```jldoctest
789 julia> v = [3, 1, 2, 1];
790
791 julia> v[partialsortperm(v, 1)]
792 1
793
794 julia> p = partialsortperm(v, 1:3)
795 3-element view(::Array{Int64,1}, 1:3) with eltype Int64:
796 2
797 4
798 3
799
800 julia> v[p]
801 3-element Array{Int64,1}:
802 1
803 1
804 2
805 ```
806 """
807 partialsortperm(v::AbstractVector, k::Union{Integer,OrdinalRange}; kwargs...) =
808 partialsortperm!(similar(Vector{eltype(k)}, axes(v,1)), v, k; kwargs..., initialized=false)
809
810 """
811 partialsortperm!(ix, v, k; by=<transform>, lt=<comparison>, rev=false, initialized=false)
812
813 Like [`partialsortperm`](@ref), but accepts a preallocated index vector `ix` the same size as
814 `v`, which is used to store (a permutation of) the indices of `v`.
815
816 If the index vector `ix` is initialized with the indices of `v` (or a permutation thereof), `initialized` should be set to
817 `true`.
818
819 If `initialized` is `false` (the default), then `ix` is initialized to contain the indices of `v`.
820
821 If `initialized` is `true`, but `ix` does not contain (a permutation of) the indices of `v`, the behavior of
822 `partialsortperm!` is undefined.
823
824 (Typically, the indices of `v` will be `1:length(v)`, although if `v` has an alternative array type
825 with non-one-based indices, such as an `OffsetArray`, `ix` must also be an `OffsetArray` with the same
826 indices, and must contain as values (a permutation of) these same indices.)
827
828 Upon return, `ix` is guaranteed to have the indices `k` in their sorted positions, such that
829
830 ```julia
831 partialsortperm!(ix, v, k);
832 v[ix[k]] == partialsort(v, k)
833 ```
834
835 The return value is the `k`th element of `ix` if `k` is an integer, or view into `ix` if `k` is
836 a range.
837
838 # Examples
839 ```jldoctest
840 julia> v = [3, 1, 2, 1];
841
842 julia> ix = Vector{Int}(undef, 4);
843
844 julia> partialsortperm!(ix, v, 1)
845 2
846
847 julia> ix = [1:4;];
848
849 julia> partialsortperm!(ix, v, 2:3, initialized=true)
850 2-element view(::Array{Int64,1}, 2:3) with eltype Int64:
851 4
852 3
853 ```
854 """
855 function partialsortperm!(ix::AbstractVector{<:Integer}, v::AbstractVector,
856 k::Union{Integer, OrdinalRange};
857 lt::Function=isless,
858 by::Function=identity,
859 rev::Union{Bool,Nothing}=nothing,
860 order::Ordering=Forward,
861 initialized::Bool=false)
862 if axes(ix,1) != axes(v,1)
863 throw(ArgumentError("The index vector is used as a workspace and must have the " *
864 "same length/indices as the source vector, $(axes(ix,1)) != $(axes(v,1))"))
865 end
866 if !initialized
867 @inbounds for i = axes(ix,1)
868 ix[i] = i
869 end
870 end
871
872 # do partial quicksort
873 sort!(ix, PartialQuickSort(k), Perm(ord(lt, by, rev, order), v))
874
875 maybeview(ix, k)
876 end
877
878 ## sortperm: the permutation to sort an array ##
879
880 """
881 sortperm(v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
882
883 Return a permutation vector `I` that puts `v[I]` in sorted order. The order is specified
884 using the same keywords as [`sort!`](@ref). The permutation is guaranteed to be stable even
885 if the sorting algorithm is unstable, meaning that indices of equal elements appear in
886 ascending order.
887
888 See also [`sortperm!`](@ref).
889
890 # Examples
891 ```jldoctest
892 julia> v = [3, 1, 2];
893
894 julia> p = sortperm(v)
895 3-element Array{Int64,1}:
896 2
897 3
898 1
899
900 julia> v[p]
901 3-element Array{Int64,1}:
902 1
903 2
904 3
905 ```
906 """
907 function sortperm(v::AbstractVector;
908 alg::Algorithm=DEFAULT_UNSTABLE,
909 lt=isless,
910 by=identity,
911 rev::Union{Bool,Nothing}=nothing,
912 order::Ordering=Forward)
913 ordr = ord(lt,by,rev,order)
914 if ordr === Forward && isa(v,Vector) && eltype(v)<:Integer
915 n = length(v)
916 if n > 1
917 min, max = extrema(v)
918 (diff, o1) = sub_with_overflow(max, min)
919 (rangelen, o2) = add_with_overflow(diff, oneunit(diff))
920 if !o1 && !o2 && rangelen < div(n,2)
921 return sortperm_int_range(v, rangelen, min)
922 end
923 end
924 end
925 ax = axes(v, 1)
926 p = similar(Vector{eltype(ax)}, ax)
927 for (i,ind) in zip(eachindex(p), ax)
928 p[i] = ind
929 end
930 sort!(p, alg, Perm(ordr,v))
931 end
932
933
934 """
935 sortperm!(ix, v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false)
936
937 Like [`sortperm`](@ref), but accepts a preallocated index vector `ix`. If `initialized` is `false`
938 (the default), `ix` is initialized to contain the values `1:length(v)`.
939
940 # Examples
941 ```jldoctest
942 julia> v = [3, 1, 2]; p = zeros(Int, 3);
943
944 julia> sortperm!(p, v); p
945 3-element Array{Int64,1}:
946 2
947 3
948 1
949
950 julia> v[p]
951 3-element Array{Int64,1}:
952 1
953 2
954 3
955 ```
956 """
957 function sortperm!(x::AbstractVector{<:Integer}, v::AbstractVector;
958 alg::Algorithm=DEFAULT_UNSTABLE,
959 lt=isless,
960 by=identity,
961 rev::Union{Bool,Nothing}=nothing,
962 order::Ordering=Forward,
963 initialized::Bool=false)
964 if axes(x,1) != axes(v,1)
965 throw(ArgumentError("index vector must have the same length/indices as the source vector, $(axes(x,1)) != $(axes(v,1))"))
966 end
967 if !initialized
968 @inbounds for i = axes(v,1)
969 x[i] = i
970 end
971 end
972 sort!(x, alg, Perm(ord(lt,by,rev,order),v))
973 end
974
975 # sortperm for vectors of few unique integers
976 function sortperm_int_range(x::Vector{<:Integer}, rangelen, minval)
977 offs = 1 - minval
978 n = length(x)
979
980 where = fill(0, rangelen+1)
981 where[1] = 1
982 @inbounds for i = 1:n
983 where[x[i] + offs + 1] += 1
984 end
985
986 #cumsum!(where, where)
987 @inbounds for i = 2:length(where)
988 where[i] += where[i-1]
989 end
990
991 P = Vector{Int}(undef, n)
992 @inbounds for i = 1:n
993 label = x[i] + offs
994 P[where[label]] = i
995 where[label] += 1
996 end
997
998 return P
999 end
1000
1001 ## sorting multi-dimensional arrays ##
1002
1003 """
1004 sort(A; dims::Integer, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
1005
1006 Sort a multidimensional array `A` along the given dimension.
1007 See [`sort!`](@ref) for a description of possible
1008 keyword arguments.
1009
1010 To sort slices of an array, refer to [`sortslices`](@ref).
1011
1012 # Examples
1013 ```jldoctest
1014 julia> A = [4 3; 1 2]
1015 2×2 Array{Int64,2}:
1016 4 3
1017 1 2
1018
1019 julia> sort(A, dims = 1)
1020 2×2 Array{Int64,2}:
1021 1 2
1022 4 3
1023
1024 julia> sort(A, dims = 2)
1025 2×2 Array{Int64,2}:
1026 3 4
1027 1 2
1028 ```
1029 """
1030 function sort(A::AbstractArray;
1031 dims::Integer,
1032 alg::Algorithm=DEFAULT_UNSTABLE,
1033 lt=isless,
1034 by=identity,
1035 rev::Union{Bool,Nothing}=nothing,
1036 order::Ordering=Forward)
1037 dim = dims
1038 order = ord(lt,by,rev,order)
1039 n = length(axes(A, dim))
1040 if dim != 1
1041 pdims = (dim, setdiff(1:ndims(A), dim)...) # put the selected dimension first
1042 Ap = permutedims(A, pdims)
1043 Av = vec(Ap)
1044 sort_chunks!(Av, n, alg, order)
1045 permutedims(Ap, invperm(pdims))
1046 else
1047 Av = A[:]
1048 sort_chunks!(Av, n, alg, order)
1049 reshape(Av, axes(A))
1050 end
1051 end
1052
1053 @noinline function sort_chunks!(Av, n, alg, order)
1054 inds = LinearIndices(Av)
1055 for s = first(inds):n:last(inds)
1056 sort!(Av, s, s+n-1, alg, order)
1057 end
1058 Av
1059 end
1060
1061 """
1062 sort!(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
1063
1064 Sort the multidimensional array `A` along dimension `dims`.
1065 See [`sort!`](@ref) for a description of possible keyword arguments.
1066
1067 To sort slices of an array, refer to [`sortslices`](@ref).
1068
1069 !!! compat "Julia 1.1"
1070 This function requires at least Julia 1.1.
1071
1072 # Examples
1073 ```jldoctest
1074 julia> A = [4 3; 1 2]
1075 2×2 Array{Int64,2}:
1076 4 3
1077 1 2
1078
1079 julia> sort!(A, dims = 1); A
1080 2×2 Array{Int64,2}:
1081 1 2
1082 4 3
1083
1084 julia> sort!(A, dims = 2); A
1085 2×2 Array{Int64,2}:
1086 1 2
1087 3 4
1088 ```
1089 """
1090 function sort!(A::AbstractArray;
1091 dims::Integer,
1092 alg::Algorithm=defalg(A),
1093 lt=isless,
1094 by=identity,
1095 rev::Union{Bool,Nothing}=nothing,
1096 order::Ordering=Forward)
1097 ordr = ord(lt, by, rev, order)
1098 nd = ndims(A)
1099 k = dims
1100
1101 1 <= k <= nd || throw(ArgumentError("dimension out of range"))
1102
1103 remdims = ntuple(i -> i == k ? 1 : size(A, i), nd)
1104 for idx in CartesianIndices(remdims)
1105 Av = view(A, ntuple(i -> i == k ? Colon() : idx[i], nd)...)
1106 sort!(Av, alg, ordr)
1107 end
1108 A
1109 end
1110
1111 ## fast clever sorting for floats ##
1112
1113 module Float
1114 using ..Sort
1115 using ...Order
1116 using ..Base: @inbounds, AbstractVector, Vector, last, axes
1117
1118 import Core.Intrinsics: slt_int
1119 import ..Sort: sort!
1120 import ...Order: lt, DirectOrdering
1121
1122 const Floats = Union{Float32,Float64}
1123
1124 struct Left <: Ordering end
1125 struct Right <: Ordering end
1126
1127 left(::DirectOrdering) = Left()
1128 right(::DirectOrdering) = Right()
1129
1130 left(o::Perm) = Perm(left(o.order), o.data)
1131 right(o::Perm) = Perm(right(o.order), o.data)
1132
1133 lt(::Left, x::T, y::T) where {T<:Floats} = slt_int(y, x)
1134 lt(::Right, x::T, y::T) where {T<:Floats} = slt_int(x, y)
1135
1136 isnan(o::DirectOrdering, x::Floats) = (x!=x)
1137 isnan(o::Perm, i::Integer) = isnan(o.order,o.data[i])
1138
1139 function nans2left!(v::AbstractVector, o::Ordering, lo::Integer=first(axes(v,1)), hi::Integer=last(axes(v,1)))
1140 i = lo
1141 @inbounds while i <= hi && isnan(o,v[i])
1142 i += 1
1143 end
1144 j = i + 1
1145 @inbounds while j <= hi
1146 if isnan(o,v[j])
1147 v[i], v[j] = v[j], v[i]
1148 i += 1
1149 end
1150 j += 1
1151 end
1152 return i, hi
1153 end
1154 function nans2right!(v::AbstractVector, o::Ordering, lo::Integer=first(axes(v,1)), hi::Integer=last(axes(v,1)))
1155 i = hi
1156 @inbounds while lo <= i && isnan(o,v[i])
1157 i -= 1
1158 end
1159 j = i - 1
1160 @inbounds while lo <= j
1161 if isnan(o,v[j])
1162 v[i], v[j] = v[j], v[i]
1163 i -= 1
1164 end
1165 j -= 1
1166 end
1167 return lo, i
1168 end
1169
1170 nans2end!(v::AbstractVector, o::ForwardOrdering) = nans2right!(v,o)
1171 nans2end!(v::AbstractVector, o::ReverseOrdering) = nans2left!(v,o)
1172 nans2end!(v::AbstractVector{<:Integer}, o::Perm{<:ForwardOrdering}) = nans2right!(v,o)
1173 nans2end!(v::AbstractVector{<:Integer}, o::Perm{<:ReverseOrdering}) = nans2left!(v,o)
1174
1175 issignleft(o::ForwardOrdering, x::Floats) = lt(o, x, zero(x))
1176 issignleft(o::ReverseOrdering, x::Floats) = lt(o, x, -zero(x))
1177 issignleft(o::Perm, i::Integer) = issignleft(o.order, o.data[i])
1178
1179 function fpsort!(v::AbstractVector, a::Algorithm, o::Ordering)
1180 i, j = lo, hi = nans2end!(v,o)
1181 @inbounds while true
1182 while i <= j && issignleft(o,v[i]); i += 1; end
1183 while i <= j && !issignleft(o,v[j]); j -= 1; end
1184 i <= j || break
1185 v[i], v[j] = v[j], v[i]
1186 i += 1; j -= 1
1187 end
1188 sort!(v, lo, j, a, left(o))
1189 sort!(v, i, hi, a, right(o))
1190 return v
1191 end
1192
1193
1194 fpsort!(v::AbstractVector, a::Sort.PartialQuickSort, o::Ordering) =
1195 sort!(v, first(axes(v,1)), last(axes(v,1)), a, o)
1196
1197 sort!(v::AbstractVector{<:Floats}, a::Algorithm, o::DirectOrdering) = fpsort!(v,a,o)
1198 sort!(v::Vector{Int}, a::Algorithm, o::Perm{<:DirectOrdering,<:Vector{<:Floats}}) = fpsort!(v,a,o)
1199
1200 end # module Sort.Float
1201
1202 end # module Sort