# On sorting in an array-less language

This is partly a programming and partly a combinatorics question.

I'm working in a language that unfortunately doesn't support array structures. I've run into a problem where I need to sort my variables in increasing order.

Since the language has functions for the minimum and maximum of two inputs (but the language does not allow me to nest them, e.g. min(a, min(b, c)) is disallowed), I thought this might be one way towards my problem.

If, for instance, I have two variables $a$ and $b$, I only need one temporary variable so that $a$ ends up being less than or equal to $b$:

t = min(a, b);
b = max(a, b);
a = t;


for three variables $a,b,c$, the situation is a little more complicated, but only one temporary variable still suffices so that $a \leq b \leq c$:

a = min(a, b);
t = max(a, b);
c = max(t, c);
t = min(t, c);
b = max(a, t);
a = min(a, t);


Not having a strong combinatorics background, however, I don't know how to generalize the above constructions if I have $n$ variables in general. In particular, is there a way to figure out how many temporary variables I would need to sort out $n$ variables, and to figure out what is the minimum number of assignment statements needed for sorting?

-
Out of curiosity, what programming language are you using? – GEL Jul 21 '11 at 17:22

Many sorting algorithms work by performing a sequence of swaps, so you need only one extra variable to implement them for any fixed $n$. What you're doing is effectively unrolling the entire algorithm loop into a sequence of conditional assignments.
The number of assignments will be three times the number of swaps, and I think the exact number may depend on the sorting algorithm. It'll be on the order of $n \log n$, though.