Javascript : natural sort of alphanumerical strings

I'm looking for the easiest way to sort an array that consists of numbers and text, and a combination of these.

E.g.

'123asd'
'19asd'
'12345asd'
'asd123'
'asd12'

turns into

'19asd'
'123asd'
'12345asd'
'asd12'
'asd123'

This is going to be used in combination with the solution to another question I've asked here.

The sorting function in itself works, what I need is a function that can say that that '19asd' is smaller than '123asd'.

I'm writing this in JavaScript.

Edit: as adormitu pointed out, what I'm looking for is a function for natural sorting

This is now possible in modern browsers using localeCompare. By passing the numeric: true option, it will smartly recognize numbers. You can do case-insensitive using sensitivity: 'base'. Tested in Chrome, Firefox, and IE11.

Here's an example. It returns 1, meaning 10 goes after 2:

'10'.localeCompare('2', undefined, {numeric: true, sensitivity: 'base'})

For performance when sorting large numbers of strings, the article says:

> When comparing large numbers of strings, such as in sorting large arrays, it is better to create an Intl.Collator object and use the function provided by its compare property. Docs link

var collator = new Intl.Collator(undefined, {numeric: true, sensitivity: 'base'});
var myArray = ['1_Document', '11_Document', '2_Document'];
console.log(myArray.sort(collator.compare));

If you have a array of objects you can do like this:

myArrayObjects = myArrayObjects.sort(function(a, b) {
  return a.name.localeCompare(b.name, undefined, {
    numeric: true,
    sensitivity: 'base'
  });
});

var myArrayObjects = [{    "id": 1,    "name": "1 example"  },  {    "id": 2,    "name": "100 example"  },  {    "id": 3,    "name": "12 example"  },  {    "id": 4,    "name": "5 example"  },]

myArrayObjects = myArrayObjects.sort(function(a, b) {
  return a.name.localeCompare(b.name, undefined, {
    numeric: true,
    sensitivity: 'base'
  });
});
console.log(myArrayObjects);

To compare values you can use a comparing method-

function naturalSorter(as, bs){
	var a, b, a1, b1, i= 0, n, L,
	rx=/(\.\d+)|(\d+(\.\d+)?)|([^\d.]+)|(\.\D+)|(\.$)/g;
	if(as=== bs) return 0;
	a= as.toLowerCase().match(rx);
	b= bs.toLowerCase().match(rx);
	L= a.length;
	while(i<L){
		if(!b[i]) return 1;
		a1= a[i],
		b1= b[i++];
		if(a1!== b1){
			n= a1-b1;
			if(!isNaN(n)) return n;
			return a1>b1? 1:-1;
		}
	}
	return b[i]? -1:0;
}

But for speed in sorting an array, rig the array before sorting, so you only have to do lower case conversions and the regular expression once instead of in every step through the sort.

function naturalSort(ar, index){
	var L= ar.length, i, who, next, 
	isi= typeof index== 'number', 
	rx=  /(\.\d+)|(\d+(\.\d+)?)|([^\d.]+)|(\.(\D+|$))/g;
	function nSort(aa, bb){
		var a= aa[0], b= bb[0], a1, b1, i= 0, n, L= a.length;
		while(i<L){
			if(!b[i]) return 1;
			a1= a[i];
			b1= b[i++];
			if(a1!== b1){
				n= a1-b1;
				if(!isNaN(n)) return n;
				return a1>b1? 1: -1;
			}
		}
		return b[i]!= undefined? -1: 0;
	}
	for(i= 0; i<L; i++){
		who= ar[i];
		next= isi? ar[i][index] || '': who;
		ar[i]= [String(next).toLowerCase().match(rx), who];
	}
	ar.sort(nSort);
	for(i= 0; i<L; i++){
		ar[i]= ar[i][1];
	}
}

Imagine a number-zero-padding function n => n.padStart(8, "0") that takes any number and pads it, i.e.

• "19" -> "00000019"
• "123" -> "00000123"

This function can be used to help sort the "19" string so that it appears before the "123" string.

Let's add a regex /\d+/g creating the natural expansion function str => str.replace(/\d+/g, n => n.padStart(8, "0")) which finds only number sections in a string and pads them, i.e.

• "19asd" -> "00000019asd"
• "123asd" -> "00000123asd"

Now, we can use this natural expansion function to help implement natural order sort:

const list = [
    "123asd",
    "19asd",
    "12345asd",
    "asd123",
    "asd12"
];

const ne = str => str.replace(/\d+/g, n => n.padStart(8, "0"));
const nc = (a,b) => ne(a).localeCompare(ne(b));

console.log(list.map(ne).sort()); // intermediate values
console.log(list.sort(nc); // result

The intermediate results demonstrated by list.map(ne).sort() show what the ne natural expansion function does. It implements number-zero-padding on only the number portions of the string and leaves the alphabet components unchanged.

[  "00000019asd",  "00000123asd",  "00012345asd",  "asd00000012",  "asd00000123"]

The final version of solution implements a natural order comparator nc implemented as (a,b) => ne(a).localeCompare(ne(b)) and uses it in list.sort(nc) so things get ordered correctly:

[  "19asd",  "123asd",  "12345asd",  "asd12",  "asd123"]

The most fully-featured library to handle this as of 2019 seems to be natural-orderby.

import { orderBy } from 'natural-orderby'

const unordered = [
  '123asd',
  '19asd',
  '12345asd',
  'asd123',
  'asd12'
]

const ordered = orderBy(unordered)

// [ '19asd',
//   '123asd',
//   '12345asd',
//   'asd12',
//   'asd123' ]

It not only takes arrays of strings, but also can sort by the value of a certain key in an array of objects. It can also automatically identify and sort strings of: currencies, dates, currency, and a bunch of other things.

Surprisingly, it's also only 1.6kB when gzipped.

Building on @Adrien Be's answer above and using the code that Brian Huisman & David koelle created, here is a modified prototype sorting for an array of objects:

//Usage: unsortedArrayOfObjects.alphaNumObjectSort("name");
//Test Case: var unsortedArrayOfObjects = [{name: "a1"}, {name: "a2"}, {name: "a3"}, {name: "a10"}, {name: "a5"}, {name: "a13"}, {name: "a20"}, {name: "a8"}, {name: "8b7uaf5q11"}];
//Sorted: [{name: "8b7uaf5q11"}, {name: "a1"}, {name: "a2"}, {name: "a3"}, {name: "a5"}, {name: "a8"}, {name: "a10"}, {name: "a13"}, {name: "a20"}]

// **Sorts in place**
Array.prototype.alphaNumObjectSort = function(attribute, caseInsensitive) {
  for (var z = 0, t; t = this[z]; z++) {
    this[z].sortArray = new Array();
    var x = 0, y = -1, n = 0, i, j;

    while (i = (j = t[attribute].charAt(x++)).charCodeAt(0)) {
      var m = (i == 46 || (i >=48 && i <= 57));
      if (m !== n) {
        this[z].sortArray[++y] = "";
        n = m;
      }
      this[z].sortArray[y] += j;
    }
  }

  this.sort(function(a, b) {
    for (var x = 0, aa, bb; (aa = a.sortArray[x]) && (bb = b.sortArray[x]); x++) {
      if (caseInsensitive) {
        aa = aa.toLowerCase();
        bb = bb.toLowerCase();
      }
      if (aa !== bb) {
        var c = Number(aa), d = Number(bb);
        if (c == aa && d == bb) {
          return c - d;
        } else {
          return (aa > bb) ? 1 : -1;
        }
      }
    }

    return a.sortArray.length - b.sortArray.length;
  });

  for (var z = 0; z < this.length; z++) {
    // Here we're deleting the unused "sortArray" instead of joining the string parts
    delete this[z]["sortArray"];
  }
}