O(n^2) is bad - can it be fixed?

[Andrew Dalke]

Ben Wolfson wrote:
>      if really_like_off_topic:
>
>          F'rinstance, some Spanish-speaking countries.  It annoys me
>          greatly when bookstores file books by Gabriel Garcia Marquez
>          under the 'M's instead of 'G's.

Down that path lies what to me seems madness.

Take a look at Knuth, The Art of Computer Programming, v.3
("Sorting and Searching"), problem 17 on p7.

17. [33] (Library card sorting.)  ... The following "alphabetical"
listing indicates may of the procedures recommended in the American
Library Association Rules for Filing Catalog Cars (Chicago: 1942):

    Text of card                    Remarks
R. Accademia nazionale dei     Ignore foreign royalty (except British)
  Lincei, Rome.
1812; ein historischer Roman.  Achtzehnhundert zw"olf
Biblioth`eque d'histoire       Treat apostrophe as space in French
  re'volutionnaire.
 ...
Brown, Mrs. J. Crosby          Ignore designation of rank
Brown, John                    Names with dates follow those without
Brown, John, mathematician     ... and the latter are subarranged
Brown, John, of Boston           by descriptibe words
Brown, John, 1716-1766         Arrange identical names by birthdate
BROWN, JOHN, 1715-1766         Works "about" follow works "By"
Brown, John, d. 1811           Sometimes birthdate must be estimated
  ...
Dix, Morgan, 1827-1908         Names precede words
1812 ouverture                 Dix-huit cent douze
Le XIXe si`ele franc,ais       Die-neuvi`eme
The 1847 issue of U.S. stamps  Eighteen forty-seven
1812 overture                  Eighteen twelve
 ...   _    _
al-Khuwarizmi,    _ _          Ignore initial "al-" in Arabic names
    Muhammad ibn Musa
 ...
McCarthy, John, 1927-          Mc = Mac
 ...
Mrs. Dalloway                  "Mrs." = "Mistress"
 ...
Ste-Marie, Gaston P            Sainte
 ...


If each book was assigned a unique number, would you be annoyed?
(Eg, Dewey decimal or Library of Congress ordering.)  So do what
I do and treat bookstores as using some arbitary ordering scheme,
but where the key just happens to be somewhat guessable from
knowledge of the author.

No so very much different from the skill I once had with Dewey
decimal where I could figure out at least which case the book
was on given a description of it content.  (Granted, it was a
small library, but not all that small.)

                    Andrew
                    dalke at acm.org