Built-in sorting algorithms in APIs seldom sort text string in the order expected by humans, for example when looking up a word in a dictionary or the yellow pages.

Here is an example:

Builtin sort
Alpha 100
Alpha 2
Alpha 200
Alpha 2A
Alpha 2A-8000
Alpha 2A-900

Natural sort
Alpha 2
Alpha 2A
Alpha 2A-900
Alpha 2A-8000
Alpha 100
Alpha 200

Devise an algorithm that sorts a list of strings in the natural sort order!

Hint: Split each input row in groups of letters and groups of integers, and compare rows group-by-group. You might want to divide the problem into subproblems, each with its own class and tests!