Trying to eliminate stack overflow during recursion (Alphabetic Bubble Sorter)

Question

I was looking at this question, Order table by row alphabeticaly, and thought, "that OP needs some sort of bubble sorter."

I had done a numerical bubble sorter here, Using LaTeX to compact a list of numbers (it actually sorted reference numbers and also compacted sequential references) and saw that I had also done an alpha-bubble sorter, as well here, Sorting a comma-separated list with LaTeX?.

Unfortunately, I discovered that the alpha-bubble sorter was prone to stack overflow from the recursion, when the list became larger. So I endeavored to streamline things here, rewriting the code. It is able to handle larger list sizes than the cited version, but as seen the included MWE, if I uncomment that one additional item in the list (encontrar), I blow the stack.

Now I know that, in theory, the way to avoid blowing the stack during a conditional recursion is to ...\expandafter\recursion\fi. However, I've never been good at mastering that technique when the recursion is nested deep in an \if block, nor when the recursion is not a mere macro name, but instead a ...\recursion<data-block>\relax\fi blob.

David C tells me that the stack size is set in texmf.cnf, and while I haven't yet found that file in my MikTeX installation, I realize that enlarging the stack is a poor fix in lieu of better code.

I also have not yet put in the \the\lccode tweaks to overlook lettercase in the search, but one thing at a time.

I figure a general LaTeX alpha-bubble sorter would be a useful thing to more than just me, so I post it here as a question, in hopes that it can be beat into submission and become a useful tool.

In the MWE below, the routine \alphabubblesorter calls on \sortlist to do the primary bubble sort, with \picknext being called upon for cases that share the same first letter. So \sortlist is recursive through the data list, and \picknext is recursive through the letter list of two comparitive entries.

\documentclass[10pt]{article}
\newcommand\alphabubblesort[1]{\def\sortedlist{}\expandafter\sortlist#1,9,\relax}
\def\sortlist#1#2,#3#4,#5\relax{%
  \ifnum`#3=`9\relax%
    \edef\sortedlist{\sortedlist#1#2}%
  \else
    \ifnum`#1<`#3\relax%
      \edef\sortedlist{\sortedlist#1#2,}%
      \sortlist#3#4,#5\relax%
    \else%
      \ifnum`#1>`#3\relax%
        \let\tmp\sortedlist%
        \def\sortedlist{}%
        \expandafter\sortlist\tmp#3#4,#1#2,#5\relax%
      \else%
        \picknext#2!,#4!\relax%
        \if F\flipflop%
          \edef\sortedlist{\sortedlist#1#2,}%
          \sortlist#3#4,#5\relax%
        \else%
          \let\tmp\sortedlist%
          \def\sortedlist{}%
          \expandafter\sortlist\tmp#3#4,#1#2,#5\relax%
        \fi%
      \fi%
    \fi%
  \fi%
}
\def\picknext#1#2,#3#4\relax{%
  \ifnum`#1<`#3\relax
    \xdef\flipflop{F}%
  \else%
    \ifnum`#1>`#3\relax%
      \xdef\flipflop{T}%
    \else%
      \picknext#2!,#4!\relax%
    \fi%
  \fi%
}
\begin{document}
\alphabubblesort{da,cc,ca,eda,edc,edb,ef,ec,ed,eb,edzq,ba,e,fa,waaa,wa,qa}\sortedlist

\def\mydata{%
Spanish     ,
ser         ,
haber       ,
estar       ,
tener       ,
hacer       ,
poder       ,
decir       ,
ir          ,
ver         ,
dar         ,
saber       ,
querer      ,
llegar      ,
pasar       ,
deber       ,
poner       ,
parecer     ,
quedar      ,
creer       ,
hablar      ,
llevar      ,
dejar       ,
seguir      ,
%encontrar   ,
llamar       }
\alphabubblesort{\mydata}\sortedlist
\end{document}

Answer 1

something like this allows the parameter stack to be popped before the recursive call

\documentclass[10pt]{article}
\newcommand\alphabubblesort[1]{\def\sortedlist{}\expandafter\sortlist#1,zzzzzzzzzz,\relax}
\def\sortlist#1#2,#3#4,#5\relax{%
  \let\next\relax
  \ifnum`#3=`z\relax%
    \edef\sortedlist{\sortedlist#1#2}%
  \else
    \ifnum`#1<`#3\relax%
      \edef\sortedlist{\sortedlist#1#2,}%
      \def\next{\sortlist#3#4,#5\relax}%
    \else%
      \ifnum`#1>`#3\relax%
        \let\tmp\sortedlist%
        \def\sortedlist{}%
        \def\next{\expandafter\sortlist\tmp#3#4,#1#2,#5\relax}%
      \else%
        \picknext#2!,#4!\relax%
        \if F\flipflop%
          \edef\sortedlist{\sortedlist#1#2,}%
           \def\next{\sortlist#3#4,#5\relax}%
        \else%
          \let\tmp\sortedlist%
          \def\sortedlist{}%
          \def\next{\expandafter\sortlist\tmp#3#4,#1#2,#5\relax}%
        \fi%
      \fi%
    \fi%
  \fi%
\next
}
\def\picknext#1#2,#3#4\relax{%
  \ifnum`#1<`#3\relax
    \xdef\flipflop{F}%
  \else%
    \ifnum`#1>`#3\relax%
      \xdef\flipflop{T}%
    \else%
      \ZZfifi{\picknext#2!,#4!\relax}%
    \fi%
  \fi%
}

\def\ZZfifi#1\fi\fi{\fi\fi#1}

\begin{document}
\alphabubblesort{30,2c,2a,4da,4dc,4db,4f,4c,4d,2b,4dzq,10,4,50,W0,w0,q0}\sortedlist

\def\mydata{%
Spanish     ,
ser         ,
haber       ,
estar       ,
tener       ,
hacer       ,
poder       ,
decir       ,
ir          ,
ver         ,
dar         ,
saber       ,
querer      ,
llegar      ,
pasar       ,
deber       ,
poner       ,
parecer     ,
quedar      ,
creer       ,
hablar      ,
llevar      ,
dejar       ,
seguir      ,
encontrar   ,
llamar       }
\alphabubblesort{\mydata}\sortedlist
\end{document}

---

I hate to meddle in David's amazing answer (Steven here), but I realized I could streamline things further by going directly to \picknext. I also added the \the\lccode bit to screen out lettercase.

So, in this incarnation, \sortlist merely performs the swap of two adjacent list items, if appropriate, whereas \picknext makes the decision on whether the swap should be made. (\sortlist no longer compares anything except for the end of list condition).

Since David was too modest to lay out the specifics of his changes, I will just call reader attention to his use of \next, which is a not so unusual way of moving stuff outside of a nested \if structure. But the crowning glory comes with his creation and use of \ZZfifi, which (if I understand it) absorbs the remaining two \fis of the current recursion, and then pops 2 of them off the stack as the first step in the next recursion. Masterful!

\documentclass[10pt]{article}
\newcommand\alphabubblesort[1]{\def\sortedlist{}\expandafter\sortlist#1,\cr,\relax}
\def\sortlist#1,#2,#3\relax{%
  \let\next\relax
  \ifx\cr#2\relax%
    \edef\sortedlist{\sortedlist#1}%
  \else
    \picknext#1!,#2!\relax%
    \if F\flipflop%
      \edef\sortedlist{\sortedlist#1,}%
      \def\next{\sortlist#2,#3\relax}%
    \else%
      \let\tmp\sortedlist%
      \def\sortedlist{}%
      \def\next{\expandafter\sortlist\tmp#2,#1,#3\relax}%
    \fi%
  \fi%
\next
}
\def\picknext#1#2,#3#4\relax{%
  \ifnum\the\lccode`#1<\the\lccode`#3\relax
    \xdef\flipflop{F}%
  \else%
    \ifnum\the\lccode`#1>\the\lccode`#3\relax%
      \xdef\flipflop{T}%
    \else%
      \ZZfifi{\picknext#2!,#4!\relax}%
    \fi%
  \fi%
}
\def\ZZfifi#1\fi\fi{\fi\fi#1}
\begin{document}
\alphabubblesort{da,cc,ca,eda,edc,edb,ef,ec,ed,eb,edzq,ba,e,fa,waaa,wa,qa}\sortedlist

\def\mydata{
Spanish, ser, haber, estar, tener, hacer, poder, decir, ir, ver, dar, saber, querer,
llegar, pasar, deber, poner, parecer, quedar, creer, hablar, llevar, dejar,
seguir, encontrar, llamar}
\alphabubblesort{\mydata}\sortedlist
\end{document}