```
is.sorted(a)
testSort(n = 1000)
bubbleSort(a)
insertionSort(a)
selectionSort(a)
shellSort(a, f = 2.3)
heapSort(a)
mergeSort(a, m = 10)
mergeOrdered(a, b)
quickSort(a, m = 3)
quickSortx(a, m = 25)
```

a, b

Numeric vectors to be sorted or merged.

f

Retracting factor for

`shellSort`

.m

Size of subsets that are sorted by

`insertionSort`

when the
sorting procedure is called recursively.n

Only in

`testSort`

: the length of a vector of random numbers
to be sorted.-
All routines return the vector sorted.

`is.sorted`

indicates logically whether the vector is sorted.
`bubbleSort(a)`

is the well-known ``bubble sort'' routine; it is
forbiddingly slow. `insertionSort(a)`

sorts the array one entry at a time; it is slow,
but quite efficient for small data sets.

`selectionSort(a)`

is an in-place sorting routine that is inefficient,
but noted for its simplicity.

`shellSort(a, f = 2.3)`

exploits the fact that insertion sort works
efficiently on input that is already almost sorted. It reduces the gaps
by the factor `f`

; `f=2.3`

is said to be a reasonable choice.

`heapSort(a)`

is not yet implemented.

`mergeSort(a, m = 10)`

works recursively, merging already sorted parts
with `mergeOrdered`

. `m`

should be between`3`

and 1/1000 of
the size of `a`

.

`mergeOrdered(a, b)`

works only correctly if `a`

and `a`

are already sorted.

`quickSort(a, m = 3)`

realizes the celebrated ``quicksort algorithm''
and is the fastest of all implementations here. To avoid too deeply nested
recursion with R, `insertionSort`

is called when the size of a subset
is smaller than `m`

.
Values between `3..30`

seem reasonable and smaller values are better,
with the risk of running into a too deeply nested recursion.

`quickSort(a, m = 25)`

is an extended version where the split is
calculated more carefully, but in general this approach takes too much
time.

Values for `m`

are `20..40`

with `m=25`

favoured.

`testSort(n = 1000)`

is a test routine, e.g. for testing your
computer power. On an iMac, `quickSort`

will sort an array of
size 1,000,000 in less than 15 secs.

`sort`

, the internal C-based sorting routine.
```
## Not run:
# testSort(100)
#
# a <- sort(runif(1000)); b <- sort(runif(1000))
# system.time(y <- mergeSort(c(a, b)))
# system.time(y <- mergeOrdered(a, b))
# is.sorted(y)## End(Not run)
```

Run the code above in your browser using DataLab