Course the recursion strategy, the space complexity is O(lgn). Maybe the bottom-up merge sort will work?