import re
re_natural = re.compile('[0-9]+|[^0-9]+')
def natural_key2(s):
parts = re_natural.findall(s)
natural = [(1, int(c)) if c.isdigit() else (0, c.lower()) for c in parts]
ties_alpha = [c for c in parts if not c.isdigit()]
ties_numeric = [c for c in parts if c.isdigit()]
return natural + [(-1,)] + ties_alpha + ties_numeric
test_cases = [
# (unsorted list, sorted list)
(list('bca'), ['a', 'b', 'c']),
(list('CbA'), ['A', 'b', 'C']),
(list('r0B9a'), ['a', 'B', 'r', '0', '9']),
(['a2', '1a', '10a', 'a1', 'a100'], ['a1', 'a2', 'a100', '1a', '10a']),
(['GAM', 'alp2', 'ALP11', '1', 'alp100', 'alp10', '100', 'alp1', '2'],
['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']),
(list('ra0b9A'), ['A', 'a', 'b', 'r', '0', '9']),
(['Abc', 'abc', 'ABc'], ['ABc', 'Abc', 'abc']),
(['0A', '00a', 'a', 'A', 'A0', '00A', '0', 'a0', '00', '0a'],
['A', 'a', 'A0', 'a0', '0', '00', '0A', '00A', '0a', '00a'])
]
for case in test_cases:
print(case[1])
print(sorted(case[0], key=natural_key2))
aW1wb3J0IHJlCgpyZV9uYXR1cmFsID0gcmUuY29tcGlsZSgnWzAtOV0rfFteMC05XSsnKQoKZGVmIG5hdHVyYWxfa2V5MihzKToKICAgIHBhcnRzID0gcmVfbmF0dXJhbC5maW5kYWxsKHMpCiAgICBuYXR1cmFsID0gWygxLCBpbnQoYykpIGlmIGMuaXNkaWdpdCgpIGVsc2UgKDAsIGMubG93ZXIoKSkgZm9yIGMgaW4gcGFydHNdCiAgICB0aWVzX2FscGhhID0gW2MgZm9yIGMgaW4gcGFydHMgaWYgbm90IGMuaXNkaWdpdCgpXQogICAgdGllc19udW1lcmljID0gIFtjIGZvciBjIGluIHBhcnRzIGlmIGMuaXNkaWdpdCgpXQogICAgcmV0dXJuIG5hdHVyYWwgKyBbKC0xLCldICsgdGllc19hbHBoYSArIHRpZXNfbnVtZXJpYwoKdGVzdF9jYXNlcyA9IFsKICAgICMgKHVuc29ydGVkIGxpc3QsIHNvcnRlZCBsaXN0KQogICAgKGxpc3QoJ2JjYScpLCBbJ2EnLCAnYicsICdjJ10pLAogICAgKGxpc3QoJ0NiQScpLCBbJ0EnLCAnYicsICdDJ10pLAogICAgKGxpc3QoJ3IwQjlhJyksIFsnYScsICdCJywgJ3InLCAnMCcsICc5J10pLAogICAgKFsnYTInLCAnMWEnLCAnMTBhJywgJ2ExJywgJ2ExMDAnXSwgWydhMScsICdhMicsICdhMTAwJywgJzFhJywgJzEwYSddKSwKICAgIChbJ0dBTScsICdhbHAyJywgJ0FMUDExJywgJzEnLCAnYWxwMTAwJywgJ2FscDEwJywgJzEwMCcsICdhbHAxJywgJzInXSwKICAgICAgICBbJ2FscDEnLCAnYWxwMicsICdhbHAxMCcsICdBTFAxMScsICdhbHAxMDAnLCAnR0FNJywgJzEnLCAnMicsICcxMDAnXSksCiAgICAobGlzdCgncmEwYjlBJyksIFsnQScsICdhJywgJ2InLCAncicsICcwJywgJzknXSksCiAgICAoWydBYmMnLCAnYWJjJywgJ0FCYyddLCBbJ0FCYycsICdBYmMnLCAnYWJjJ10pLAogICAgKFsnMEEnLCAnMDBhJywgJ2EnLCAnQScsICdBMCcsICcwMEEnLCAnMCcsICdhMCcsICcwMCcsICcwYSddLAogICAgICAgIFsnQScsICdhJywgJ0EwJywgJ2EwJywgJzAnLCAnMDAnLCAnMEEnLCAnMDBBJywgJzBhJywgJzAwYSddKQpdCgpmb3IgY2FzZSBpbiB0ZXN0X2Nhc2VzOgogICAgcHJpbnQoY2FzZVsxXSkKICAgIHByaW50KHNvcnRlZChjYXNlWzBdLCBrZXk9bmF0dXJhbF9rZXkyKSkK
['a', 'b', 'c']
['a', 'b', 'c']
['A', 'b', 'C']
['A', 'b', 'C']
['a', 'B', 'r', '0', '9']
['a', 'B', 'r', '0', '9']
['a1', 'a2', 'a100', '1a', '10a']
['a1', 'a2', 'a100', '1a', '10a']
['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']
['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']
['A', 'a', 'b', 'r', '0', '9']
['A', 'a', 'b', 'r', '0', '9']
['ABc', 'Abc', 'abc']
['ABc', 'Abc', 'abc']
['A', 'a', 'A0', 'a0', '0', '00', '0A', '00A', '0a', '00a']
['A', 'a', 'A0', 'a0', '0', '00', '0A', '00A', '0a', '00a']