// TODO
Sequence of characters (immutable)
String vs. StringBuilder
Quadratic time
1 | public static String reverse(String s) { |
Linear time
1 | public static String reverse(String s) { |
Assumption. Keys are integers between 0 and R - 1.
Goal. Sort an array a[] of N integers between 0 and R - 1.
Implementation.
1 | int N = a.length; |
Proposition. Key-indexed counting uses ~ 11 N + 4 R array accesses to sort N items whose keys are integers between 0 and R - 1.
Most-signiﬁcant-digit-ﬁrst string sort
Treat strings as if they had an extra char at end (smaller than any char).
implementation
potential for disastrous performance