bit sort

fast sorting of integers

bit_sort(x, decreasing = FALSE, na.last = NA, has.dup = TRUE)

Arguments

x

an integer vector

decreasing

(currently only FALSE is supported)

na.last

NA removes NAs, FALSE puts NAs at the beginning, TRUE puts NAs at the end

has.dup

TRUE (the default) assumes that x might have duplicates, set to FALSE if duplicates are impossible

Value

a sorted vector

Details

determines the range of the integers and checks if the density justifies use of a bit vector; if yes, sorts the first occurences of each integer in the range using a bit vector, sorts the rest and merges; if no, falls back to quicksort.

See also

sort(), ramsort(), bit_sort_unique()

Examples

bit_sort(c(2L, 1L, NA, NA, 1L, 2L))
#> [1] 1 1 2 2
bit_sort(c(2L, 1L, NA, NA, 1L, 2L), na.last=FALSE)
#> [1] NA NA  1  1  2  2
bit_sort(c(2L, 1L, NA, NA, 1L, 2L), na.last=TRUE)
#> [1]  1  1  2  2 NA NA

if (FALSE) { # \dontrun{
x <- sample(1e7, replace=TRUE)
system.time(bit_sort(x))
system.time(sort(x))
} # }