Естественная сортировка строк на JavaScript

Вообще compareStrings функция имеет смысл и отдельно использовать — когда хочется использовать объектный, а не процедурный синтаксис.

И такой вопрос: а сколько раз выполняется парсер для каждой строки из массива? Может имеет смысл кешировать разобранные фрагменты?

После первых двух абзацев решил себя проверить, написал функцию сравнения:

function compareStrings(str1, str2) {
	var rx = /([^\d]+|\d+)/ig;
	var str1split = str1.match( rx );
	var str2split = str2.match( rx );
	for(var i=0, l=Math.min(str1split.length, str2split.length); i < l; i++) {
		var s1 = str1split[i], 
		    s2 = str2split[i];
		if (s1 === s2) continue;
		if (isNaN(+s1) || isNaN(+s2))
			return s1 > s2 ? 1 : -1;
		else
			return +s1 - s2;		
	}
	return 0;
}
console.log( [ 'file2', 'file10', 'file1' ].sort(compareStrings) );

На оптимальность так же не претендует. Подход простой, разбиваем строку на массив — строки одтельно числа отдельно ( 't123est' ~> ['t', '123', 'est'] ), и затем сравниваем каждый элемент получившихся массивов как строки и числа соотв.

Еще один велосипед, этот C-style :)

1. function isDigit(ch) {
2.   var code = ch.charCodeAt(0);
3.   return code >= '0'.charCodeAt(0) && code <= '9'.charCodeAt(0);
4. }
5.  
6. function readDigits(s, i0) {
7.   var result = 0;
8.   for (var i = i0; i < s.length; i++) {
9.     var digit = s.charCodeAt(i) - '0'.charCodeAt(0);
10.     if (digit < 0 || digit > 9) break;
11.     result = result * 10 + digit;
12.   }
13.   return { number: result, position: i };
14. }
15.  
16. function strnatcmp(s1, s2) {
17.   var i1 = 0;
18.   var i2 = 0;
19.   while (true) {
20.     if (i1 >= s1.length) return i2 >= s2.length ? 0 : -1;
21.     if (i2 >= s2.length) return 1;
22.  
23.     var ch1 = s1.charAt(i1);
24.     var ch2 = s2.charAt(i2);
25.  
26.     if (isDigit(ch1)) {
27.       if (!isDigit(ch2)) return -1;
28.  
29.       var n1 = readDigits(s1, i1);
30.       var n2 = readDigits(s2, i2);
31.  
32.       if (n1.number < n2.number) return -1;
33.       if (n1.number > n2.number) return 1;
34.  
35.       i1 = n1.position;
36.       i2 = n2.position;
37.       continue;
38.     }
39.     
40.     if (isDigit(ch2)) return 1;
41.     if (ch1 < ch2) return -1;
42.     if (ch1 > ch2) return 1;
43.  
44.     i1++;
45.     i2++;
46.   }
47. }

* This source code was highlighted with Source Code Highlighter.

Если бы мне срочно потребовался натуральный поиск, я бы сделал что то вроде. Жаль, что такое решение не сработает на строках типа 'word444port';

var test_arr = ['file10', 'file222', 'file2', 'file1', 'file'];

test_arr.sort(function(a, b){
    return a.replace(/\d+/, '') >= b.replace(/\d+/, '') && +a.replace(/\D+/, '') >= +b.replace(/\D+/, '')
})

Когда то я решил эту задачу тем, что сначала создал копию каждой строки, заменив числа в ней на числа фиксированной длинны (благо для строк где цифр было слишком много натуральная сортировка была не критична), т.е. 'sd4zx92' -> 'sd0004zx0092', а потом сортировал полученный массив штатным способом (на самом деле сортировал массив индексов, чтобы в результате все таки получить старые строки).

p.p.s. чем то ваш вариант с кешированием похож на мой

FYI, реализация этой штуки в WebKit (Web Inspector): WebCore/inspector/front-end/ObjectPropertiesSection.js