Natural sort - where digit parts sort as digits, and the rest sort alphabetically. I've found that everyone gets this; it's a little more real than tic-tac-toe or some of the others, but not terribly challenging, and it TDDs quite cleanly.
Update Here are some test cases, by request:
public void testSimpleStrings() throws Exception {
String[] strings = new String[] {"abd", "abc"};
String[] sorted = new String[] {"abc", "abd"};
Arrays.sort(strings, new NaturalComparator());
assertEqualArrays(strings, sorted);
}
public void testComplexStrings() throws Exception {
String[] strings = new String[] {"a5", "a20"};
String[] sorted = new String[] {"a5", "a20"};
Arrays.sort(strings, new NaturalComparator());
assertEqualArrays(strings, sorted);
}
public void testDifferentSizedStrings() throws Exception {
String[] strings = new String[] {"a5a", "a5"};
String[] sorted = new String[] {"a5", "a5a"};
Arrays.sort(strings, new NaturalComparator());
assertEqualArrays(strings, sorted);
}
private void assertEqualArrays(String[] strings, String[] sorted) {
assertEquals(Arrays.asList(sorted), Arrays.asList(strings));
}
My own implementation led me to Chunks, a ChunkIterator and a ChunkComparator, and those all got their own test classes as well - but this exercise can go in a number of directions.