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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
# design criteria:
# Generic code is expenisve wrt code size!
# So the implementation should be small.
# The sort should be stable.
#
proc sort[T](arr: var openArray[T], lo, hi: natural) =
var k = 0
if lo < hi:
var mid = (lo + hi) div 2
sort(arr, lo, mid)
inc(mid)
sort(arr, mid, hi)
while lo < mid and mid <= hi:
if arr[lo] < arr[mid]:
inc(lo)
else:
when swapIsExpensive(T):
var help = arr[mid]
for k in countdown(mid, succ(lo)):
arr[k] = arr[pred(k)]
arr[lo] = help
else:
for k in countdown(mid, succ(lo)):
swap(arr[k], arr[pred(k)])
inc(lo)
inc(mid)
type
TSortOrder* = enum
Descending = -1,
Ascending = 0
proc flip(x: int, order: TSortOrder): int {.inline.} =
result = x xor ord(order) - ord(order)
# We use a fixed size stack. This size is larger
# than can be overflowed on a 64-bit machine
const
stackSize = 66
minRunSize = 7
type
TRun = tuple[index, length: int]
TSortState[T] {.pure, final.} = object
storage: seq[T]
runs: array[0..stackSize-1, TRun]
stackHeight: int # The index of the first unwritten element of the stack.
partitionedUpTo, length: int
# We keep track of how far we've partitioned up
# to so we know where to start the next partition.
# The idea is that everything < partionedUpTo
# is on the stack, everything >= partionedUpTo
# is not yet on the stack. When partitionedUpTo == length
# we'll have put everything on the stack.
proc reverse[T](a: var openArray[T], first, last: int) =
for j in first .. < first+length div 2: swap(a[j], a[length-j-1])
proc insertionSort[T]( int xs[], int length) =
for i in 1.. < length:
# The array before i is sorted. Now insert xs[i] into it
var x = xs[i]
var j = i-1
# Move j down until it's either at the beginning or on
# something <= x, and everything to the right of it has
# been moved up one.
while j >= 0 and xs[j] > x:
xs[j+1] = xs[j]
dec j
xs[j+1] = x
proc boostRunLength(s: TSortState, run: var TRun) =
# Need to make sure we don't overshoot the end of the array
var length = min(s.length - run.index, minRunSize)
insertionSort(run.index, length)
run.length = length
proc nextPartition[T](a: var openarray[T], s: var TSortState): bool =
if s.partitionedUpTo >= s.length: return false
var startIndex = s.partitionedUpTo
# Find an increasing run starting from startIndex
var nextStartIndex = startIndex + 1
if nextStartIndex < s.length:
if a[nextStartIndex] < a[startIndex]:
# We have a decreasing sequence starting here.
while nextStartIndex < s.length:
if a[nextStartIndex] < a[nextStartIndex-1]: inc(nextStartIndex)
else: break
# Now reverse it in place.
reverse(a, startIndex, nextStartIndex)
else:
# We have an increasing sequence starting here.
while nextStartIndex < s.length:
if a[nextStartIndex] >= a[nextStartIndex-1]: inc(nextStartIndex)
else: break
# So now [startIndex, nextStartIndex) is an increasing run.
# Push it onto the stack.
var runToAdd: TRun = (startIndex, nextStartIndex - startIndex)
if runToAdd.length < minRunSize:
boostRunLength(s, runToAdd)
s.partitionedUpTo = startIndex + runToAdd.length
s.runs[s.stackHeight] = runToAdd
inc s.stackHeight
result = true
proc shouldCollapse(s: TSortState): bool =
if s.stackHeight > 2:
var h = s.stackHeight-1
var headLength = s.runs[h].length
var nextLength = s.runs[h-1].length
result = 2 * headLength > nextLength
proc merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]) =
# Merge the sorted arrays p1, p2 of length l1, l2 into a single
# sorted array starting at target. target may overlap with either
# of p1 or p2 but must have enough space to store the array.
# Use the storage argument for temporary storage. It must have room for
# l1 + l2 ints.
int *merge_to = storage
# Current index into each of the two arrays we're writing
# from.
int i1, i2;
i1 = i2 = 0;
# The address to which we write the next element in the merge
int *next_merge_element = merge_to;
# Iterate over the two arrays, writing the least element at the
# current position to merge_to. When the two are equal we prefer
# the left one, because if we're merging left, right we want to
# ensure stability.
# Of course this doesn't matter for integers, but it's the thought
# that counts.
while i1 < l1 and i2 < l2:
if p1[i1] <= p2[i2]:
*next_merge_element = p1[i1];
i1++
else:
*next_merge_element = p2[i2];
i2++
next_merge_element++
# If we stopped short before the end of one of the arrays
# we now copy the rest over.
memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));
# We've now merged into our additional working space. Time
# to copy to the target.
memcpy(target, merge_to, sizeof(int) * (l1 + l2));
proc mergeCollapse(a: s: var TSortState) =
var X = s.runs[s.stackHeight-2]
var Y = s.runs[s.stackHeight-1]
merge(X.index, X.index, X.length, Y.index, Y.length, s.storage)
dec s.stackHeight
inc X.length, Y.length
s.runs[s.stackHeight-1] = X
proc sort[T](arr: var openArray[T], first, last: natural,
cmp: proc (x,y: T): int, order = TSortOrder.ascending) =
var s: TSortState
newSeq(s.storage, arr.len)
s.stackHeight = 0
s.partitionedUpTo = 0
s.length = arr.len
while nextPartition(s):
while shouldCollapse(s): mergeCollapse(s)
while s.stackHeight > 1: mergeCollapse(s)
proc sort[T](arr: var openArray[T], cmp: proc (x, y: T): int = cmp,
order = TSortOrder.ascending) =
sort(arr, 0, high(arr), order)
|