1using System;
2using System.Collections.Generic;
3using System.Text.RegularExpressions;
4
5public class NaturalComparer : Comparer<string>, IDisposable
6{
7	private Dictionary<string, string[]> table;
8
9	public NaturalComparer()
10	{
11		table = new Dictionary<string, string[]>();
12	}
13
14	public void Dispose()
15	{
16		table.Clear();
17		table = null;
18	}
19
20	public override int Compare(string x, string y)
21	{
22		if(x == y)
23		{
24			return 0;
25		}
26		string[] x1, y1;
27		if(!table.TryGetValue(x, out x1))
28		{
29			x1 = Regex.Split(x.Replace(" ", ""), "([0-9]+)");
30			table.Add(x, x1);
31		}
32		if(!table.TryGetValue(y, out y1))
33		{
34			y1 = Regex.Split(y.Replace(" ", ""), "([0-9]+)");
35			table.Add(y, y1);
36		}
37
38		for(int i = 0; i < x1.Length && i < y1.Length; i++)
39		{
40			if(x1[i] != y1[i])
41			{
42				return PartCompare(x1[i], y1[i]);
43			}
44		}
45		if(y1.Length > x1.Length)
46		{
47			return 1;
48		}
49		else if(x1.Length > y1.Length)
50		{
51			return -1;
52		}
53		else
54		{
55			return 0;
56		}
57	}
58
59	private static int PartCompare(string left, string right)
60	{
61		int x, y;
62		if(!int.TryParse(left, out x))
63		{
64			return left.CompareTo(right);
65		}
66
67		if(!int.TryParse(right, out y))
68		{
69			return left.CompareTo(right);
70		}
71
72		return x.CompareTo(y);
73	}
74}

List testItems = new List(new string[]
			                                          	{
			                                          		"z24", "z2", "z15", "z1",
			                                          		"z 21", "z22", "1", "2", "5", "3", "abc1", "abc92", "abc9", "abc9z4",
			                                          		"z3", "z20", "a5", "z11",
			                                          	});
			testItems.Sort(new NaturalComparer());
			foreach(string _item in testItems)
			{
				Console.WriteLine(_item);
			}