# How to sort an alphanumeric list

I have been trying to find a package or a method to sort lists of names in an easy manner in TeX/LaTeX. I have tried some of the routines in the xfor package, as well as looked at some of the new macros in LaTeX3 but was not very successful with either of them.

I have come with the idea of using the MakeIndex program to sort and categorize. It is available with every distribution and the LaTeX class is very short and easily hackable being approximately 36 lines long (including the glossary macros that I can eliminate) and a few more definitions for styling in the basic book or article class.

Here is a minimal example that sorts a list of names by profession (category).

\documentclass[11pt]{article}
\usepackage{makeidx}
\def\addName#1#2{\index{Name!#1}\index{#2!#1}}
\makeindex
\begin{document}
\renewcommand{\indexname}{Famous and Infamous Sorted People}
\addName{Leslie Lamport}{Computer Scientist}
\addName{Donald Knuth}{Computer Scientist}
\addName{Tim Berners Lee}{Computer Scientist}
\addName{Brian Kernighan}{Computer Scientist}
\addName{Noam Chomsky}{Linguist}
\addName{Yiannis Lazarides}{Lifelong Trainee \protect\TeX nician}
\addName{Leonard Euler}{Mathematician}
\addName{Carl Friendrich Gauss}{Mathematician}
\addName{August Ferdinard M\"{o}bius}{Mathematician}

%% Importing the .ind file rather than use \printindex
%% so we do not need to redefine the command
%%
\input{indextest.ind}

\begin{verbatim}
\begin{theindex}
\item Lifelong Trainee \TeX nician
\subitem Yiannis Lazarides, 1
\item Linguist
\subitem Noam Chomsky, 1
\end{theindex}
\end{verbatim}
\end{document}


Is this a good idea? Are there any packages devoted to alphanumeric sorting? I know it can easily be done with an external script, but I am looking for a TeX/LaTeX solution. Do you think it is a good approach?

-
With my LaTeX3 hat on, I'd point out that we've not really needed sorting yet, hence the somewhat limited support. Perhaps you could outline what might be useful, say on the LaTeX-list. –  Joseph Wright Dec 13 '10 at 9:30
Do you just want a list or are you also going to reference the names in your document? If so, you might want to have a look at datagidx (part of the datatool bundle). However, as it uses TeX to do the sorting, it's a lot slower than using makeindex. –  Nicola Talbot Jan 7 at 20:12

## 5 Answers

I didn't look at Charles's code because I wanted to see how difficult it would be to implement a generic sorting macro that was expandable. It turns out that it's more or less straight-forward to do in a continuation-passing style.

\documentclass{article}
\usepackage{etoolbox}
\makeatletter
% #1 - comparator
% #2 - token list to sort
\newcommand\sort[2]{%
\ifstrempty{#2}
{}% else
{%
\sort@begin#1{}#2\sort@s\sort@begin
}%
}

% helpers
\def\sort@s{\sort@s}
\def\ifsort@s#1{%
\ifx\sort@s#1%
\expandafter\@firstoftwo
\else
\expandafter\@secondoftwo
\fi
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - rest of the list
\def\sort@begin#1#2#3#4\sort@begin{%
\ifsort@s{#4}
{%
\sortend{#3}%
\sort#1{#2}%
}% else
{%
\sort@go#1{#2}{#3}#4\sort@go
}%
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - token under consideration
% #5 - rest of the list
\def\sort@go#1#2#3#4#5\sort@go{%
#1{#3}{#4}{\sort@output#1{#2}{#5}}%
}
% #1 - comparator
% #2 - tokens processed so far
% #3 - rest of the list
% #4 - smaller of the two tokens
% #5 - larger of the two tokens
\def\sort@output#1#2#3#4#5{%
\ifsort@s{#3}
{%
\sortoutput{#4}%
\sort#1{#2{#5}}%
}% else
{%
\sort@begin#1{#2{#5}}{#4}#3\sort@begin
}%
}

\def\sort@numlt#1#2#3{%
\ifnumcomp{#1}<{#2}
{#3{#1}{#2}}% else
{#3{#2}{#1}}%
}

\def\sort@numgt#1#2#3{%
\ifnumcomp{#1}>{#2}
{#3{#1}{#2}}% else
{#3{#2}{#1}}%
}

\def\sort@alpha#1#2#3{%
\ifnumcomp{\pdfstrcmp{#1}{#2}}<{0}
{#3{#1}{#2}}% else
{#3{#2}{#1}}%
}

\newcommand*\sortnumlt{\sort\sort@numlt}
\newcommand*\sortnumgt{\sort\sort@numgt}
\newcommand*\sortalpha{\sort\sort@alpha}
\makeatother

% Change these to change out the sort outputs.
\newcommand*\sortoutput[1]{#1, }
\newcommand*\sortend[1]{#1.}
\begin{document}
\sortnumgt{87632147{55}9{8/2}}

\sortalpha{{Goodbye}{Cruel}{World}}

\renewcommand*\sortoutput[1]{#1}
\renewcommand*\sortend[1]{#1}
\edef\temp{\sortnumlt{87632147{55}9}}
\texttt{\meaning\temp}
\end{document}


I hope the code is readable. I tried to document the arguments to each function. In particular, the first argument to \sort is a comparator control sequence that must take three arguments. The first two are the two elements of the following list to compare and the third is the continuation. Basically, the comparator should expand to either #3{#1}{#2} or #3{#2}{#1} depending on #1 being "less than" #2.

I've implemented three such comparators. The first two compare lists of numbers whereas the third does alphanumeric string comparison using \pdfstrcmp. Since the number comparisons use \ifnumcomp from etoolbox, you can use arbitrary arithmetic expressions for the elements, hence {8/2} in the list.

Finally, to show that this is expandable (at least it is whenever the comparator, \sortoutput, and \sortend are), \temp is defined using \edef and its meaning is typeset to ensure that it has been set to the appropriate value: macro:->12346778955.

Note that it would also be straight-forward to thread \sortoutput and \sortend through all of these macros so that multiple \sorts could be used in the same expansion. I just didn't think about adding those until I had written all of the rest of the code (more or less).

Note further that this is selection sort and thus would take Θ(n2) time, even in the best case. However, this being TeX and it having to construct the token lists for each argument each time, I think this implementation is actually Θ(n3) time. So don't try it on large lists.

-
@TH Impressive. I will give it a try a bit later. Speed is not really a problem with the application I am busy with. –  Yiannis Lazarides Dec 14 '10 at 15:10
@TH there is a question from a new user who can't comment here tex.stackexchange.com/questions/101979/… –  David Carlisle Mar 11 '13 at 19:26

The following certainly works for one list, but I am not certain as to how to extend it to more than one sorted list.

\documentclass[a4paper,12pt]{report}
\usepackage{datatool}
\usepackage[top=2cm, bottom=2cm, left=1cm, right=1cm]{geometry}
\usepackage[spanish]{babel}
\usepackage{amsfonts,amssymb,amsmath}

\newcommand{\sortitem}[2]{%
\DTLnewrow{list}%
\DTLnewdbentry{list}{label}{#1}%
\DTLnewdbentry{list}{description}{#2}%
}

\newenvironment{sortedlist}{%
\DTLifdbexists{list}{\DTLcleardb{list}}{\DTLnewdb{list}}%
}{%
\DTLsort{label}{list}%
\begin{description}%
\DTLforeach*{list}{\theLabel=label,\theDesc=description}{%
\item[\theLabel] \theDesc }%
\end{description}%
}

\begin{document}
\begin{sortedlist}
\sortitem{Leonard Euler}{Mathematician}
\sortitem{Carl Friedrich Gauss}{Mathematician}
\sortitem{August Ferdinand M"\obius}{Mathematician}
\end{sortedlist}
\end{document}

-
Welcome to TeX.sx! A tip: If you indent lines by 4 spaces, then they are marked as a code sample. You can also highlight the code and click the "code" button (with "{}" on it). –  Michael Ummels Jul 5 '11 at 7:01

If you are willing to use LuaLaTeX, then you it should be possible to port the various language specific sorting functions from ConTeXt MkIV. For example see

-

A long time ago, I wrote a sorting package for LaTeX, for personal use. I have no idea how to use it or whether it works, but here is the source code:

http://www.eecs.harvard.edu/~cduan/download/?file=sortlist.sty

It requires a helper file, located at http://www.eecs.harvard.edu/~cduan/download/?file=strings.sty

-
@Charles Thanks, code looks very neat, I will give it a try a bit later ... and welcome to the community. –  Yiannis Lazarides Dec 13 '10 at 6:13

I started using TH's code, and found that it had to be tweaked a bit for my use case. Specifically, I wanted to be able to sort things with \par in them, and wanted the sort order to be based on the value of a \ref. After struggling for a bit, I got something working, and figured it would be worth sharing my efforts here. An example document that uses it looks like this:

\documentclass{article}
\usepackage{sort}
\begin{document}
\newcounter{foo}
\refstepcounter{foo}\label{a}
\refstepcounter{foo}\label{b}

\begin{trivlist}
\sortref{%
{{a}{Text with some proofs about part a

in multiple paragraphs!}}%
{{b}{Proofs about

the other part}}%
}
\end{trivlist}
\end{document}



\usepackage{etoolbox}
\usepackage{refcount}
\makeatletter
% #1 - comparator
% #2 - token list to sort
\newcommand\sort[2]{%
\ifstrempty{#2}
{}% else
{%
\sort@begin#1{}#2\sort@s\sort@begin
}%
}

% helpers
\def\sort@s{\sort@s}
\long\def\ifsort@s#1{%
\ifx\sort@s#1%
\expandafter\@firstoftwo
\else
\expandafter\@secondoftwo
\fi
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - rest of the list
\long\def\sort@begin#1#2#3#4\sort@begin{%
\ifsort@s{#4}
{%
\sortend{#3}%
\sort#1{#2}%
}% else
{%
\sort@go#1{#2}{#3}#4\sort@go
}%
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - token under consideration
% #5 - rest of the list
\long\def\sort@go#1#2#3#4#5\sort@go{%
#1{#3}{#4}{\sort@output#1{#2}{#5}}%
}
% #1 - comparator
% #2 - tokens processed so far
% #3 - rest of the list
% #4 - smaller of the two tokens
% #5 - larger of the two tokens
\long\def\sort@output#1#2#3#4#5{%
\ifsort@s{#3}
{%
\sortoutput{#4}%
\sort#1{#2{#5}}%
}% else
{%
\sort@begin#1{#2{#5}}{#4}#3\sort@begin
}%
}

\def\sort@numlt#1#2#3{%
\ifnumcomp{#1}<{#2}
{#3{#1}{#2}}% else
{#3{#2}{#1}}%
}

\def\sort@numgt#1#2#3{%
\ifnumcomp{#1}>{#2}
{#3{#1}{#2}}% else
{#3{#2}{#1}}%
}

\def\sort@alpha#1#2#3{%
\ifnumcomp{\pdfstrcmp{#1}{#2}}<{0}
{#3{#1}{#2}}% else
{#3{#2}{#1}}%
}

\long\def\fst#1#2{#1}
\long\def\snd#1#2{#2}
\long\def\sort@ref#1#2#3{%
% Since #1 and #2 frequently contain newlines in their \snd part, and
% \getrefnumber is not \long, we must take care to remove any newlines
% *before* supplying an argument to \getrefnumber
\edef\@leftref{\fst#1}%
\edef\@rightref{\fst#2}%
\ifnumcomp{\getrefnumber\@leftref}<{\getrefnumber\@rightref}%
{#3{#1}{#2}}%
{#3{#2}{#1}}%
}

\newcommand*\sortnumlt{\sort\sort@numlt}
\newcommand*\sortnumgt{\sort\sort@numgt}
\newcommand*\sortalpha{\sort\sort@alpha}
\newcommand\sortref{\sort\sort@ref}

% Change these to change out the sort outputs.
\newcommand\sortoutput[1]{%
% As in the definition of \sort@ref, we must take care to remove
% newlines before handing off to \ref
\edef\@refname{\fst#1}%
\item {\bf Case \ref\@refname:} \snd#1%
}
\newcommand\sortend\sortoutput

\makeatother

-