Hello.

Sometimes, you only want to sort some integers, lesser than or equal to the number of elements in a list. Then pretty much everything is overkill really, but here is a little clever algorithm I stumbled upon. It does the sorting in linear time, which is fast.

Edit

It was probably Herman Hollerith that implemented it in 1890â€™s maybe for the U.S Census. Herman Hollerith also invented the radix sort, where this algorithm might be used.

If you want one that works for k>n, then look at the post below, it is really meant for elements in the range 100, but it should be easy to modify. NB! it will perform worser than n log n, so when there are many elements in the list, or k is disproportionally large, then you are better off using Nigel Garveyâ€™s quicksort.

Not that it matters much here, when sorting single digits, but counting sort is stable. It performs itâ€™s work by counting up occurences of the digits in the original list, using the current digit in L as index of the element of C that shall be incremented. Then we accumulate the occurences in C into Cp, so, that we know the last position to put the element with that index, in the sorted array. then we work from the end, copying elements over to the new array, and decrementing the position in the â€śaccumulation of frequencies arrayâ€ť (Cp), until we are done.

My intended usage is to use it on lists with 2 to 20 elements, and k not being much larger than say 26.

```
(* Counting Sort:
Sorts positive integers larger than 0 in linear time O( k + n ) (if K=O(n) ).
That is if the largest integer in the list, k, is supposed to be less than the number of elements.
Otherwise, this algorithm won't work.
*)
set thel to {4, 1, 3, 4, 3}
countingsort(thel, 4)
on countingsort(|L|, k)
-- countingsort: origin unknown. found it in an algorithms lecture from MIT
-- Implemented in AppleScript by McUsr 2015/6/24
script o
property L : |L|
property C : missing value
property Cp : missing value
property B : missing value
end script
set ll to length of o's L
copy |L| to o's C
repeat with i from 1 to ll
set item i of o's C to 0
end repeat
repeat with i from 1 to ll
set item (item i of o's L) of o's C to (item (item i of o's L) of o's C) + 1
end repeat
copy o's C to o's Cp
repeat with i from 2 to k
set item i of o's Cp to (item (i - 1) of o's Cp) + (item i of o's C)
end repeat
copy o's C to o's B
repeat with j from ll to 1 by -1
tell item j of o's L
set item (item it of o's Cp) of o's B to it
set item it of o's Cp to (item it of o's Cp) - 1
end tell
end repeat
return o's B
end countingsort
```