96
95
takes advantage of sorted runs which exist in many real world
99
The ``sort``, ``sortr``, ``sort_by``, and ``sortperm`` functions select a reasonable
100
default algorithm, depending on the type of the target array.
98
The sort functions select a reasonable default algorithm, depending on
99
the type of the target array.
102
Mutating and non-mutating versions of the sort functions and of each
103
of the algorithm functions are exported and available for use by
101
Mutating and non-mutating versions of the sort functions using each
102
of the algorithms above are exported and available for use by
106
+-------------------+--------------------+---------+-------------------+
107
| Non-mutating | Mutating | Stable | Time Complexity |
108
+===================+====================+=========+===================+
109
| ``sort`` | ``sort!`` | (\*) | O(n log n) |
110
+-------------------+--------------------+---------+-------------------+
111
| ``sortr`` | ``sortr!`` | (\*) | O(n log n) |
112
+-------------------+--------------------+---------+-------------------+
113
| ``sort_by`` | ``sort_by!`` | (\*) | O(n log n) |
114
+-------------------+--------------------+---------+-------------------+
115
| ``sortperm`` | ``sortperm!`` | (\*) | O(n log n) |
116
+-------------------+--------------------+---------+-------------------+
117
| ``insertionsort`` | ``insertionsort!`` | yes | O(n^2) |
118
+-------------------+--------------------+---------+-------------------+
119
| ``quicksort`` | ``quicksort!`` | no | O(n log n) |
120
+-------------------+--------------------+---------+-------------------+
121
| ``mergesort`` | ``mergesort!`` | yes | O(n log n) |
122
+-------------------+--------------------+---------+-------------------+
123
| ``timsort`` | ``timsort!`` | yes | <= O(n log n) |
124
+-------------------+--------------------+---------+-------------------+
126
(\*) Stability depends on the algorithm for the target array data type.
128
In addition to the exported functions shown in the table, each of the
129
algorithms also has an additional set of unexported functions for
130
reverse sorting, sorting by a function of the data, and for the stable
131
sorts, function varieties which return a permutation in addition to
132
the sorted array. These are shown in the table below.
134
+----------------------+---------------------------+----------------------------+--------------------------+
135
| Sort | Non-mutating Variation | Mutating Variation | Function |
136
+======================+===========================+============================+==========================+
137
| ``insertionsort`` | ``insertionsort_r`` | ``insertionsort_r!`` | Reverse sort |
138
+----------------------+---------------------------+----------------------------+--------------------------+
139
| | ``insertionsort_by`` | ``insertionsort_by!`` | Sort by function |
140
+----------------------+---------------------------+----------------------------+--------------------------+
141
| | ``insertionsort_perm`` | ``insertionsort_perm!`` | Permutation sort |
142
+----------------------+---------------------------+----------------------------+--------------------------+
143
| | ``insertionsort_perm_r`` | ``insertionsort_perm_r!`` | Reverse permutation sort |
144
+----------------------+---------------------------+----------------------------+--------------------------+
145
| | ``insertionsort_perm_by`` | ``insertionsort_perm_by!`` | Permutation sort by func |
146
+----------------------+---------------------------+----------------------------+--------------------------+
147
| ``mergesort`` | ``mergesort_r`` | ``mergesort_r!`` | Reverse sort |
148
+----------------------+---------------------------+----------------------------+--------------------------+
149
| | ``mergesort_by`` | ``mergesort_by!`` | Sort by function |
150
+----------------------+---------------------------+----------------------------+--------------------------+
151
| | ``mergesort_perm`` | ``mergesort_perm!`` | Permutation sort |
152
+----------------------+---------------------------+----------------------------+--------------------------+
153
| | ``mergesort_perm_r`` | ``mergesort_perm_r!`` | Reverse permutation sort |
154
+----------------------+---------------------------+----------------------------+--------------------------+
155
| | ``mergesort_perm_by`` | ``mergesort_perm_by!`` | Permutation sort by func |
156
+----------------------+---------------------------+----------------------------+--------------------------+
157
| ``timsort`` | ``timsort_r`` | ``timsort_r!`` | Reverse sort |
158
+----------------------+---------------------------+----------------------------+--------------------------+
159
| | ``timsort_by`` | ``timsort_by!`` | Sort by function |
160
+----------------------+---------------------------+----------------------------+--------------------------+
161
| | ``timsort_perm`` | ``timsort_perm!`` | Permutation sort |
162
+----------------------+---------------------------+----------------------------+--------------------------+
163
| | ``timsort_perm_r`` | ``timsort_perm_r!`` | Reverse permutation sort |
164
+----------------------+---------------------------+----------------------------+--------------------------+
165
| | ``timsort_perm_by`` | ``timsort_perm_by!`` | Permutation sort by func |
166
+----------------------+---------------------------+----------------------------+--------------------------+
167
| ``quicksort`` | ``quicksort_r`` | ``quicksort_r!`` | Reverse sort |
168
+----------------------+---------------------------+----------------------------+--------------------------+
169
| | ``quicksort_by`` | ``quicksort_by!`` | Sort by function |
170
+----------------------+---------------------------+----------------------------+--------------------------+
175
109
----------------------
176
110
General Sort Functions
177
111
----------------------
178
.. function:: sort(v)
180
Sort a vector in ascending order, according to ``isless``.
182
.. function:: sort!(v)
112
.. function:: sort(v[, dim])
114
Sort a vector in ascending order. If ``dim`` is provided, sort
115
along the given dimension.
117
.. function:: sort(lessthan, v[, dim])
119
Sort with a custom comparison function.
121
.. function:: sort(alg, ...)
123
Sort using a specific sorting algorithm (InsertionSort, QuickSort,
124
MergeSort, or TimSort).
126
.. function:: sort!(...)
186
.. function:: sortr(v)
188
Sort a vector in descending order.
190
.. function:: sortr!(v)
192
In-place sort in descending-order.
194
.. function:: sort_by(by, v)
196
Sort a vector by the result of applying function ``by``
199
.. function:: sort_by!(by, v)
201
Sort a vector in place by the result of applying function ``by``
204
.. function:: sort(a, dim)
206
Sort an array along the given dimension.
208
.. function:: sort(lessthan, a, [dim])
210
Sort with a custom comparison function.
130
.. function:: sortr(v[, dim])
132
Sort a vector in descending order. If ``dim`` is provided, sort
133
along the given dimension.
135
.. function:: sortr(alg, ...)
137
Sort in descending order with a specific sorting algorithm
138
(InsertionSort, QuickSort, MergeSort, or TimSort).
140
.. function:: sortr!(...)
144
.. function:: sortby(by, v[, dim])
146
Sort a vector according to ``by(v)``. If ``dim`` is provided,
147
sort along the given dimension.
149
.. function:: sortby(alg, ...)
151
``sortby`` using a specific sorting algorithm (``InsertionSort``,
152
``QuickSort``, ``MergeSort``, or ``TimSort``).
154
.. function:: sortby!(...)
212
158
.. function:: sortperm(v) -> s,p
214
Sort a vector in ascending order, also constructing the permutation that sorts the vector
216
.. function:: sortperm!(v) -> s,p
218
Sort a vector in ascending order in-place, also constructing the permutation that sorts the vector
220
.. function:: sortperm_r(v) -> s,p
222
Sort a vector in descending order, also constructing the permutation that sorts the vector
224
.. function:: sortperm_r!(v) -> s,p
226
Sort a vector in descending order in-place, also constructing the permutation that sorts the vector
228
.. function:: sortperm_by(by,v) -> s,p
160
Sort a vector in ascending order, also constructing the permutation
161
that sorts the vector.
163
.. function:: sortperm(lessthan, v) -> s,p
165
Sort a vector with a custom comparison function, also constructing
166
the permutation that sorts the vector.
168
.. function:: sortperm(alg, ...) -> s,p
170
``sortperm`` using a specific sorting algorithm (``InsertionSort``,
171
``QuickSort``, ``MergeSort``, or ``TimSort``).
173
.. function:: sortperm!(...) -> s,p
175
In-place ``sortperm``.
177
.. function:: sortpermr(v) -> s,p
179
Sort a vector in descending order, also constructing the
180
permutation that sorts the vector!
182
.. function:: sortpermr(alg, ...) -> s,p
184
``sortpermr`` using a specific sorting algorithm
185
(``InsertionSort``, ``QuickSort``, ``MergeSort``, or ``TimSort``).
187
.. function:: sortpermr!(v) -> s,p
189
In-place ``sortpermr``.
191
.. function:: sortpermby(by,v) -> s,p
230
193
Sort a vector according to the result of function ``by`` applied to
231
194
all values, also constructing the permutation that sorts the vector.
233
.. function:: sortperm_by!(by,v) -> s,p
235
Sort a vector in-place according to the result of function ``by``
236
applied to all values of ``v``, also constructing the permutation
237
that sorts the vector
240
---------------------------
241
Specific Sort Functions
242
---------------------------
244
.. function:: insertionsort(v[,dim])
246
Sort a vector in ascending order with insertion sort, according to ``isless``.
248
.. function:: insertionsort(lessthan,v[,dim])
250
Sort a vector in ascending order with insertion sort, using a
251
custom comparison function.
253
.. function:: insertionsort!(v[,dim])
254
.. function:: insertionsort!(v[,lo,hi])
256
In-place insertion sort, accoring to ``isless``.
258
.. function:: insertionsort!(lessthan,v[,dim])
259
.. function:: insertionsort!(lessthan,v[,lo,hi])
261
In-place insertion sort with a custom comparison function.
263
.. function:: insertionsort_r(v[,dim])
264
.. function:: insertionsort_r(v[,lo,hi])
266
Sort a vector in descending order using insertion sort.
268
.. function:: insertionsort_r!(v[,dim])
269
.. function:: insertionsort_r!(v[,lo,hi])
271
In-place insertion sort in descending order.
273
.. function:: insertionsort_by(by,v[,dim])
274
.. function:: insertionsort_by(by,v[,lo,hi])
276
Sort a vector with insertion sort according to the result of
277
function ``by`` applied to all values.
279
.. function:: insertionsort_by!(by,v[,dim])
280
.. function:: insertionsort_by!(by,v[,lo,hi])
282
Sort a vector with insertion sort in place according to the result
283
of function ``by`` applied to all values.
285
.. function:: insertionsort_perm(v[,p[,lo,hi]]) -> s,p
287
Sort a vector in ascending order, also constructing the
288
permutation that sorts the vector
290
If provided, ``p`` is an initial permutation.
292
.. function:: insertionsort_perm(lessthan,v[,p[,lo,hi]]) -> s,p
294
Sort a vector, using a custom comparison function, also
295
constructing the permutation that sorts the vector .
297
If provided, ``p`` is an initial permutation.
299
.. function:: insertionsort_perm!(v[,p[,lo,hi]])
301
Sort a vector in ascending order in-place, also constructing the
302
permutation that sorts the vector
304
If provided, ``p`` is an initial permutation.
306
.. function:: insertionsort_perm!(lessthan,v[,p[,lo,hi]])
308
Sort a vector in place, using a custom comparison function, also
309
constructing the permutation that sorts the vector .
311
If provided, ``p`` is an initial permutation.
313
.. function:: insertionsort_perm_r(v[,p,[,lo,hi]])
315
Sort a vector in descending order, also constructing the
316
permutation that sorts the vector
318
If provided, ``p`` is an initial permutation.
320
.. function:: insertionsort_perm_r!(v[,p,[,lo,hi]])
322
Sort a vector in descending order in place, also constructing the
323
permutation that sorts the vector
325
If provided, ``p`` is an initial permutation.
327
.. function:: insertionsort_perm_by(by,v[,p[,lo,hi]])
329
Sort a vector with insertion sort according to the result
330
of function ``by`` applied to all values.
332
If provided, ``p`` is an initial permutation.
334
.. function:: insertionsort_perm_by!(by,v[,p[,lo,hi]])
336
Sort a vector with insertion sort in place according to the result
337
of function ``by`` applied to all values.
339
If provided, ``p`` is an initial permutation.
342
.. function:: mergesort(v[,dim])
344
Sort a vector in ascending order with mergesort, according to ``isless``.
346
.. function:: mergesort(lessthan,v[,dim])
348
Sort a vector in ascending order with mergesort, using a
349
custom comparison function.
351
.. function:: mergesort!(v[,dim])
352
.. function:: mergesort!(v[,lo,hi])
354
In-place mergesort, accoring to ``isless``.
356
.. function:: mergesort!(lessthan,v[,dim])
357
.. function:: mergesort!(lessthan,v[,lo,hi])
359
In-place mergesort with a custom comparison function.
361
.. function:: mergesort_r(v[,dim])
362
.. function:: mergesort_r(v[,lo,hi])
364
Sort a vector in descending order using mergesort.
366
.. function:: mergesort_r!(v[,dim])
367
.. function:: mergesort_r!(v[,lo,hi])
369
In-place mergesort in descending order.
371
.. function:: mergesort_by(by,v[,dim])
372
.. function:: mergesort_by(by,v[,lo,hi])
374
Sort a vector with mergesort according to the result of
375
function ``by`` applied to all values.
377
.. function:: mergesort_by!(by,v[,dim])
378
.. function:: mergesort_by!(by,v[,lo,hi])
380
Sort a vector with mergesort in place according to the result
381
of function ``by`` applied to all values.
383
.. function:: mergesort_perm(v[,p[,lo,hi]]) -> s,p
385
Sort a vector in ascending order, also constructing the
386
permutation that sorts the vector
388
If provided, ``p`` is an initial permutation.
390
.. function:: mergesort_perm(lessthan,v[,p[,lo,hi]]) -> s,p
392
Sort a vector, using a custom comparison function, also
393
constructing the permutation that sorts the vector .
395
If provided, ``p`` is an initial permutation.
397
.. function:: mergesort_perm!(v[,p[,lo,hi]])
399
Sort a vector in ascending order in-place, also constructing the
400
permutation that sorts the vector
402
If provided, ``p`` is an initial permutation.
404
.. function:: mergesort_perm!(lessthan,v[,p[,lo,hi]])
406
Sort a vector in place, using a custom comparison function, also
407
constructing the permutation that sorts the vector .
409
If provided, ``p`` is an initial permutation.
411
.. function:: mergesort_perm_r(v[,p,[,lo,hi]])
413
Sort a vector in descending order, also constructing the
414
permutation that sorts the vector
416
If provided, ``p`` is an initial permutation.
418
.. function:: mergesort_perm_r!(v[,p,[,lo,hi]])
420
Sort a vector in descending order in place, also constructing the
421
permutation that sorts the vector
423
If provided, ``p`` is an initial permutation.
425
.. function:: mergesort_perm_by(by,v[,p[,lo,hi]])
427
Sort a vector with mergesort according to the result
428
of function ``by`` applied to all values.
430
If provided, ``p`` is an initial permutation.
432
.. function:: mergesort_perm_by!(by,v[,p[,lo,hi]])
434
Sort a vector with mergesort in place according to the result
435
of function ``by`` applied to all values.
437
If provided, ``p`` is an initial permutation.
440
.. function:: quicksort(v[,dim])
442
Sort a vector in ascending order with quicksort, according to ``isless``.
444
.. function:: quicksort(lessthan,v[,dim])
446
Sort a vector in ascending order with quicksort, using a
447
custom comparison function.
449
.. function:: quicksort!(v[,dim])
450
.. function:: quicksort!(v[,lo,hi])
452
In-place quicksort, accoring to ``isless``.
454
.. function:: quicksort!(lessthan,v[,dim])
455
.. function:: quicksort!(lessthan,v[,lo,hi])
457
In-place quicksort with a custom comparison function.
459
.. function:: quicksort_r(v[,dim])
460
.. function:: quicksort_r(v[,lo,hi])
462
Sort a vector in descending order using quicksort.
464
.. function:: quicksort_r!(v[,dim])
465
.. function:: quicksort_r!(v[,lo,hi])
467
In-place quicksort in descending order.
469
.. function:: quicksort_by(by,v[,dim])
470
.. function:: quicksort_by(by,v[,lo,hi])
472
Sort a vector with quicksort according to the result of
473
function ``by`` applied to all values.
475
.. function:: quicksort_by!(by,v[,dim])
476
.. function:: quicksort_by!(by,v[,lo,hi])
478
Sort a vector with quicksort in place according to the result
479
of function ``by`` applied to all values.
196
.. function:: sortpermby(alg, ...) -> s,p
198
``sortpermby`` using a specific sorting algorithm
199
(``InsertionSort``, ``QuickSort``, ``MergeSort``, or ``TimSort``).
201
.. function:: sortpermby!(...) -> s,p
203
In-place ``sortpermby``.
481
205
-------------------------
482
206
Sorting-related Functions
487
211
Test whether a vector is in ascending sorted order
489
.. function:: issorted_r(v)
213
.. function:: issortedr(v)
491
215
Test whether a vector is in descending sorted order
493
.. function:: issorted_by(by,v)
495
Test whether a vector is sorted by the result of function ``by``
496
applied to all values of ``v``
498
.. function:: search_sorted(a, x[, lo, hi])
500
For ``a`` sorted low to high, returns the index of the first value ``>=x``.
502
``lo`` and ``hi`` optionally limit the search range.
504
Alias for ``search_sorted_first()``
506
.. function:: search_sorted(lt, a, x[, lo, hi])
508
For ``a`` sorted using ordering function ``lt(x,y)``, returns the index of the first value equal to ``x`` or following ``x`` in the induced order
510
``lo`` and ``hi`` optionally limit the search range.
512
Alias for ``search_sorted_first()``
514
.. function:: search_sorted_r(a, x[, lo, hi])
516
For ``a`` sorted high to low, returns the index of the first value ``<=x``.
518
``lo`` and ``hi`` optionally limit the search range.
520
Alias for ``search_sorted_first_r()``
522
.. function:: search_sorted_by(by, a, x[, lo, hi])
524
For ``a`` sorted according to the natural order of ``by(x)`` for ``x`` in ``a``, returns the index of the first value equal to or following ``x`` in the induced order.
526
``lo`` and ``hi`` optionally limit the search range.
528
Alias for ``search_sorted_first_by()``
530
.. function:: search_sorted_first(a, x[, lo, hi])
532
For ``a`` sorted low to high, returns the index of the first occurance of ``x``, or if ``x`` is not in ``a``, the index of the first value following ``x`` in natural order.
534
``lo`` and ``hi`` optionally limit the search range.
536
.. function:: search_sorted_first(lt, a, x[, lo, hi])
538
For ``a`` sorted using ordering function ``lt(x,y)``, returns the index of the first occurance of ``x``, or if ``x`` is not in ``a``, the index of the first value following ``x`` in the induced order.
540
``lo`` and ``hi`` optionally limit the search range.
542
Alias for ``search_sorted_first()``
544
.. function:: search_sorted_first_r(a, x[, lo, hi])
546
For ``a`` sorted high to low, returns the index of the first occurance of ``x``, or if ``x`` is not in ``a``, the index of the first value following ``x`` in reverse natural order.
548
``lo`` and ``hi`` optionally limit the search range.
550
.. function:: search_sorted_first_by(by, a, x[, lo, hi])
552
For ``a`` sorted according to the natural order of ``by(x)`` for ``x`` in ``a``, returns the index of the first occurance of ``x``, or if ``x`` is not in ``a``, the index of the first value following ``x`` in the induced order.
554
``lo`` and ``hi`` optionally limit the search range.
556
.. function:: search_sorted_last(a, x[, lo, hi])
558
For ``a`` sorted low to high, returns the index of the last occurance of ``x``, or if ``x`` is not in ``a``, the index of the last value preceding ``x`` in natural order.
560
``lo`` and ``hi`` optionally limit the search range.
562
.. function:: search_sorted_last(lt, a, x[, lo, hi])
564
For ``a`` sorted using ordering function ``lt(x,y)``, returns the index of the last occurance of``x``, or if ``x`` is not in ``a``, the index of the last value preceding ``x`` in the induced order.
566
``lo`` and ``hi`` optionally limit the search range.
568
Alias for ``search_sorted_last()``
570
.. function:: search_sorted_last_r(a, x[, lo, hi])
572
For ``a`` sorted high to low, returns the index of the last occurance of ``x``, or if ``x`` is not in ``a``, the index of the last value preceding ``x`` in reverse natural order.
574
``lo`` and ``hi`` optionally limit the search range.
576
.. function:: search_sorted_last_by(by, a, x[, lo, hi])
578
For ``a`` sorted according to the natural order of ``by(x)`` for ``x`` in ``a``, returns the index of the last occurance of ``x``, or if ``x`` is not in ``a``, the index of the last value preceding ``x`` in the induced order.
217
.. function:: issortedby(by,v)
219
Test whether a vector is sorted according to ``by(v)``.
221
.. function:: searchsorted(a, x[, lo, hi])
223
For ``a`` sorted low to high, returns the index of the first value ``>=x``.
225
``lo`` and ``hi`` optionally limit the search range.
227
Alias for ``searchsortedfirst()``
229
.. function:: searchsorted(lt, a, x[, lo, hi])
231
For ``a`` sorted using ``lt(x,y)``, returns the index of the first value ``>=x`` according to the induced order
233
``lo`` and ``hi`` optionally limit the search range.
235
Alias for ``searchsortedfirst()``
237
.. function:: searchsortedr(a, x[, lo, hi])
239
For ``a`` sorted high to low, returns the index of the first value ``<=x``.
241
``lo`` and ``hi`` optionally limit the search range.
243
Alias for ``searchsortedfirstr()``
245
.. function:: searchsortedby(by, a, x[, lo, hi])
247
For ``a`` sorted according to ``by(a)``, returns the index of the first value ``>=x`` according to the induced order.
249
``lo`` and ``hi`` optionally limit the search range.
251
Alias for ``searchsortedfirstby()``
253
.. function:: searchsortedfirst(a, x[, lo, hi])
255
For ``a`` sorted low to high, returns the index of the first value ``>=x``.
257
``lo`` and ``hi`` optionally limit the search range.
259
.. function:: searchsortedfirst(lt, a, x[, lo, hi])
261
For ``a`` sorted using ordering function ``lt(x,y)``, returns the index of the first value ``>=x`` according to the induced order.
263
``lo`` and ``hi`` optionally limit the search range.
265
Alias for ``searchsortedfirst()``
267
.. function:: searchsortedfirstr(a, x[, lo, hi])
269
For ``a`` sorted high to low, returns the index of the first value ``<=x``.
271
``lo`` and ``hi`` optionally limit the search range.
273
.. function:: searchsortedfirstby(by, a, x[, lo, hi])
275
For ``a`` sorted according to ``by(a)``, returns the index of the first value ``>=x`` according to the induced order.
277
``lo`` and ``hi`` optionally limit the search range.
279
.. function:: searchsortedlast(a, x[, lo, hi])
281
For ``a`` sorted low to high, returns the index of the last value ``<=x``.
283
``lo`` and ``hi`` optionally limit the search range.
285
.. function:: searchsortedlast(lt, a, x[, lo, hi])
287
For ``a`` sorted low to high, returns the index of the last value ``<=x`` according to the induced order.
289
``lo`` and ``hi`` optionally limit the search range.
291
Alias for ``searchsortedlast()``
293
.. function:: searchsortedlastr(a, x[, lo, hi])
295
For ``a`` sorted high to low, returns the index of the last value ``>=x``.
297
``lo`` and ``hi`` optionally limit the search range.
299
.. function:: searchsortedlastby(by, a, x[, lo, hi])
301
For ``a`` sorted according to ``by(a)``, returns the index of the last value ``<=x`` according to the induced order.
580
303
``lo`` and ``hi`` optionally limit the search range.
added
removed
doc/stdlib/sort.rst
