-
-
Notifications
You must be signed in to change notification settings - Fork 5.5k
/
sort.jl
100 lines (91 loc) · 2.87 KB
/
sort.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# This file is a part of Julia. License is MIT: https://julialang.org/license
# reference on sorted binary search:
# http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary
# index of the first value of vector a that is greater than or equal to x;
# returns lastindex(v)+1 if x is greater than all values in v.
function searchsortedfirst(v::AbstractVector, x, lo::T, hi::T, o::Ordering)::keytype(v) where T<:Integer
hi = hi + T(1)
len = hi - lo
@inbounds while len != 0
half_len = len >>> 0x01
m = lo + half_len
if lt(o, v[m], x)
lo = m + 1
len -= half_len + 1
else
hi = m
len = half_len
end
end
return lo
end
# index of the last value of vector a that is less than or equal to x;
# returns firstindex(v)-1 if x is less than all values of v.
function searchsortedlast(v::AbstractVector, x, lo::T, hi::T, o::Ordering)::keytype(v) where T<:Integer
u = T(1)
lo = lo - u
hi = hi + u
@inbounds while lo < hi - u
m = midpoint(lo, hi)
if lt(o, x, v[m])
hi = m
else
lo = m
end
end
return lo
end
# returns the range of indices of v equal to x
# if v does not contain x, returns a 0-length range
# indicating the insertion point of x
function searchsorted(v::AbstractVector, x, ilo::T, ihi::T, o::Ordering)::UnitRange{keytype(v)} where T<:Integer
u = T(1)
lo = ilo - u
hi = ihi + u
@inbounds while lo < hi - u
m = midpoint(lo, hi)
if lt(o, v[m], x)
lo = m
elseif lt(o, x, v[m])
hi = m
else
a = searchsortedfirst(v, x, max(lo,ilo), m, o)
b = searchsortedlast(v, x, m, min(hi,ihi), o)
return a : b
end
end
return (lo + 1) : (hi - 1)
end
for s in [:searchsortedfirst, :searchsortedlast, :searchsorted]
@eval begin
$s(v::AbstractVector, x, o::Ordering) = $s(v,x,firstindex(v),lastindex(v),o)
$s(v::AbstractVector, x;
lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
$s(v,x,ord(lt,by,rev,order))
end
end
# An unstable sorting algorithm for internal use
function sort!(v::Vector; by::Function=identity, (<)::Function=<)
isempty(v) && return v # This branch is hit 95% of the time
# Of the remaining 5%, this branch is hit less than 1% of the time
if length(v) > 200 # Heap sort prevents quadratic runtime
o = ord(<, by, true)
heapify!(v, o)
for i in lastindex(v):-1:2
y = v[i]
v[i] = v[1]
percolate_down!(v, 1, y, o, i-1)
end
return v
end
@inbounds for i in 2:length(v) # Insertion sort
x = v[i]
y = by(x)
while i > 1 && y < by(v[i-1])
v[i] = v[i-1]
i -= 1
end
v[i] = x
end
v
end