I took a course about data structures and algorithms, the semester after I coded the first version of Freecell Solver. There I learned about the large complexity involved in quick-sorting, and that there was a better algorithm for merging two arrays: Merge. The Merge algorithm works like this:
Take as input two sorted arrays A and B and a result buffer R.
Keep two pointers to the arrays PA and PB, initialized to the beginning of the arrays, and a pointer PR initialized to the beginning of R.
If *PA < *PB copy *PA to *PR and increment PA. Else, copy *PB to *PR and increment PB. In any case, increment PR afterwards.
Repeat step No. 3 until PA reaches the end of A, or PB reaches the end of PB.
Copy what remains of the other array to R.
This algorithm runs in linear time. I decided to use a variation of the algorithm, due to the fact that the sort margin could become so much smaller than the main array.
In my variation, the sort margin is scanned linearly, but the index of the corresponding element in the main array is found using a binary search. Once found, all the elements up to it, are copied as is without comparison. That way, one can hopefully save a lot of comparisons.
To facilitate the merge, the sort margin was kept sorted all the times, and middle elements pushed some of the elements forward.
Lookup now is still O(log(n)), but this time insertion was reduced to O(n) time. (the merging operation is O(n) and it is done every constant number of elements) The accumulative time now is O(n2) which is O(n) multiplied by n.
This scheme ran much faster than the qsort one - by a factor of 3 or so. While the qsort() scheme was adequate to give good results most of the time, a merge of the sort margin was a much wiser choice, algorithmically.