How can I write a program to generate a sorting decision tree?

Answer 1

The kind of algorithm has been described by Charles Forgy: see the Rete algorithm. (I'm sorry, the article in WP is certainly not a quick answer but it might be a good start)

Answer 2

You might want to look into Sorting Networks. It should be possible to convert the optimal sorting network for a given number of inputs into a decision tree, I think.

Alternately, you could take a given sorting algorithm and step through it, creating a new branch at each comparison.

Finally, you could do this in reverse - for example, by taking a merge-sort type approach: Lay out all 24 possible sort orders at the bottom of the tree. Pick a comparison, and partition the leaves into two sets based on the outcome. Repeat recursively for each branch until you only have one leaf per branch.