7

As I painfully try to find a good natural sorting algorithm written in JavaScript, I then stumble upon a bunch of different implementations, interesting blog posts, and answers on StackOverflow.

Each implementation provides its technical tricks. However, the more I looked into it the more a question became very clear: "Is there actually any language-agnostic specification regarding natural sorting order of strings?"

I mean, if not, then how could one expect to write a piece of code that is actually "correct for everyone" or "agreed on by the community"? I would have expected a specification stating the result of the compromises/decisions made, at least for English, as it is simple (no accents/diacritics)...

Note that I wrote "language-agnostic" as I would expect this specification to then be used to implement solutions in different languages, not only in JavaScript, C#, or Java.

Resources:

Improve this question
7
  • 3
    “Natural Sorting” is “whatever sorting a user without any knowledge of ASCII would expect”. As such it's too subjective for an universal spec. And there are definitively a lot of corner cases one could debate endlessly about, and some parts that are difficult to get right, mostly regarding internationalization. Just draft your own algorithm, but beware of xkcd.com/927
    – amon
    Commented Sep 26, 2014 at 13:17
  • 2
    "too subjective for an universal spec", one could argue that any spec is subjective ;) "there are definitively a lot of corner cases one could debate endlessly about" yes that's why I'd want a spec so that these corner cases are covered, whether or not one think the wrong decision was taken. But as the cartoon you linked suggests, we may end up with a dozen of specs instead of one universally used. Is this better to not have any at all though? (I cannot find any...)
    – Adriano
    Commented Sep 26, 2014 at 13:29
  • 1
    Are you asking about sort algorithms or sort order? Algorithms for sorting are well understood and widely implemented in every language you're likely to use. The particular order that you want to sort things into depends heavily on your situation, but is usually tied to the character set you're using.
    – Caleb
    Commented Sep 26, 2014 at 16:47
  • 3
    Natural sort depends on the human language and the context of what you're sorting. Consider sorting kanji, or arabic text, or the former combined with latin characters. A "natural" sort of month names would probably be "Jan, Feb, ..." rather than "April, December, ...". The context matters too much for there to be an objective spec
    – Daenyth
    Commented Sep 26, 2014 at 21:38
  • 1
    @Daenyth Agreed, but I'd still like to be able to use a "context-free" string sorting implem that follows a "context-free" spec. Then I would expect different "context-specific" specifications to appear (ie. natural sorting for file names). All I'm saying here is "it'd be nice not to have to reinvent the wheel every time I want to sort a list of strings", maybe this is a frustration I have only because I'm doing this in javascript but I feel that this issue has been around for a while, see Jeff Atwood's article from 2007 blog.codinghorror.com/sorting-for-humans-natural-sort-order
    – Adriano
    Commented Sep 29, 2014 at 8:17

3 Answers 3

Reset to default
22

The algorithms for determining which string comes first when comparing two strings are called collation algorithms and the sort order they produce is called the collation order.

Unfortunately, there is no agreed upon global collation order. To make matters worse, the correct sorting order is not only language dependent, but can even differ between different contexts.
One example of language difference is that in German the accented characters are ordered immediately after their unaccented counterparts (ö comes immediately after o), but in Swedish the accented characters come right at the end of the alphabet (ö comes after z). And as for usage differences, phone books and dictionaries can have different sort orders.

Although there is no global collation order, there are collation orders that generally give a reasonable order independent of the natural language that the words are written in and there are collation algorithms that can be tailored to either give a reasonable sort order or to give the absolute correct order for a given culture and usage.

One such algorithm is the "Unicode Collation Algorithm", which can be found at http://www.unicode.org/reports/tr10/. This algorithm can be tailored for a wide range of collation orders and comes with a default configuration that gives a reasonable ordering for all Unicode codepoints. The algorithm does not depend on any particular programming language.
The introduction section of the standard gives a nice overview of the difficulties in correctly collating text.

Another algorithm is described in ISO standard 14651.

Besides the various national collation orders, there is also a standardized collation order for the European languages, called the European Ordering Rules (EOR).

Improve this answer
1
  • German has two sort orders: "Dictionary" sorting order and "Phonebook" sorting order. MacOS / iOS have an option where they introduce numbers into the sorting process, so "Chapter 8" and "Chapter 9" sort before "Chapter 10" and "Chapter 11". Unfortunately not available for Roman numbers :-( but at least I, II, III, IV, V, VI, VII, and VIII are sorted correctly automatically.
    – gnasher729
    Commented Jan 30, 2023 at 15:50
4

There is ISO 14651. This is an ISO Standard specifying an algorithm that can be used when comparing two strings. The standard also specifies a datafile specifying the comparison order, the Common Tailorable Template, CTT.

There is the European Ordering Rules. This is an implementation of the iso CTT. It defines an ordering for strings written in languages that are written with the Latin, Greek and Cyrillic alphabets.

There is the Unicode Collation Algorithm. The Unicode collation algorithm (UCA) is an algorithm defined in Unicode Technical Report #10, which defines a customizable method to compare two strings.

Improve this answer
2
  • 2
    would you mind explaining more on what these resources do and why do you recommend these as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange
    – gnat
    Commented Oct 3, 2014 at 10:39
  • 1
    @gnat I updated the answer.
    – Pieter B
    Commented Oct 3, 2014 at 10:53
0

It is certainly possible to write a collation algorithm that is equally useful for everyone - but only by being equally useless for everyone. There is a war going on between algorithms and people, as to who is the master and who is the servant.

Having has to provide the ability for users to dominate their computers, I can add to the examples given the following:

  • is CH a separate single letter coming after C in the alphabet?
  • Are O and Ó the same letter (Spanish) or different letters (Polish)?
  • Is LL a separate single letter from L?
  • and (although it isn’t collation as such) the famous exception that makes conversion to upper or lower case impossible: is a capital “i” “İ” or “I”? Is a lower-case “I” “ı” or “i”?

In the war between algorithms and people it is anyone’s guess who will win, though on the whole human servility makes a machine victory more likely.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.