brainfuck (178 bytes)
Even if brainfuck is cumbersome, it helps to work with the grain of the language. Ask yourself "Do I have to store this value explicitly in a cell?" You can often gain speed and concision by doing something more subtle. And when the value is an array index (or an arbitrary natural number), it may not fit in a cell. Of course, you could just accept that as a limit of your program. But designing your program to handle large values will often make it better in other ways.
As usual, my first working version was twice as long as it needed to be—392 bytes. Numerous modifications and two or three major rewrites produced this comparatively graceful 178-byte version. (Though amusingly a linear-time sort is only 40 bytes.)
The input values are spaced every three cells: for every (V)alue cell, there is a (L)abel cell (used for navigation) and one more cell for (S)cratch space. The overall layout of the array is
0 1 0 0 0 S V L S V L ... S V L 0 0 0 0 0 0 ...
Initially all the L cells are set to 1, to mark portions of the array that still need sorting. When we're done partitioning a subarray, we divide it into smaller subarrays by setting its pivot's L cell to 0, then locate the rightmost L cell that's still 1 and partition that subarray next. Oddly, this is all the bookkeeping we need to properly handle the recursive processing of subarrays. When all L cells have been zeroed, the whole array is sorted.
To partition a subarray, we pull its rightmost value into an S cell to act as pivot, and bring it (and the corresponding empty V cell) left, comparing it to each other value in the subarray and swapping as needed. At the end the pivot gets swapped back in, using the same swap code (which saves 50 bytes or so). During partitioning, two extra L cells are kept set to 0, to mark the two cells that may need to be swapped with each other; at the end of partitioning, the left 0 will fuse with the 0 to the left of the subarray, and the right 0 will end up marking its pivot. This process also leaves an extra 1 in the L cell to the right of the subarray; the main loop begins and ends at this cell.
>+>>>>>,[>+>>,]>+[ set up; for each subarray:
--[+<<<-]<[ find the subarray; if it exists:
[<+>-]<[ S=pivot; while pivot is in S:
<[ if not at end of subarray
->[<<<+>>>>+<-] move pivot left (and copy it)
<<[>>+>[->]<<[<]<-]> move value to S and compare with pivot
]>>>+<[[-]<[>+<-]<]>[ if pivot greater then set V=S; else:
[>>>]+<<<-<[<<[<<<]>>+>[>>>]<-] swap smaller value into V
<<[<<<]>[>>[>>>]<+<<[<<<]>-] swap S into its place
]+<<< end else and set S=1 for return path
] subarray done (pivot was swapped in)
]+[->>>]>> end "if subarray exists"; go to right
]>[brainfuck.org>>>] done sorting whole array; output it