Question: I'm trying to create an unusual associative array implementation that is very space-efficient, and I need a sorting algorithm that meets all of the following:

1. Stable (Does not change the relative ordering of elements with equal keys.)
2. In-place or almost in-place (O(log n) stack is fine, but no O(n) space usage or heap allocations.
3. O(n log n) time complexity.

Also note that the data structure to be sorted is an array.

It's easy to see that there's a basic algorithm that matches any 2 of these three (insertion sort matches 1 and 2, merge sort matches 1 and 3, heap sort matches 2 and 3), but I cannot for the life of me find anything that matches all three of these criteria.

Answer: 
There's a nice list of sorting functions [on wikipedia](http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms) that can help you find whatever type of sorting function you're after.

For example, to address your specific question, it looks like an in-place merge sort is what you want.

However, you might also want to take a look at [strand sort](http://en.wikipedia.org/wiki/Strand_sort), it's got some very interesting properties.
Perhaps [shell sort](http://en.wikipedia.org/wiki/Shell_sort)? If I recall my data structures course correctly, it tended to be stable, but it's worse case time is O(n log^2 n), although it performs O(n) on almost sorted data. It's based on insertion sort, so it sorts in place.