What is the most efficient constant-space sorting algorithm?
Consider cocktail shaker sort, which is a bidirectional version of bubble sort.  You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done.  This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final position in a single pass rather than N passes.  Also, you can keep track of the lowest and highest positions where a swap occurred; subsequent passes need not scan beyond those points.