# O(nlogn) Perfect Shuffle solution

• Refer to this paper: http://arxiv.org/pdf/0805.1598.pdf

``````class Solution(object):
def reverse(self, start, end):
low, high = start, end
while low < high:
self.nums[low], self.nums[high] = self.nums[high], self.nums[low]
low += 1
high -= 1

def getK(self, n):
k, square = 1, 3
while square - 1 <= 2 * n:
k += 1
square *= 3
return k - 1

def shuffle(self, start, end):
n = (end - start + 1) / 2

k = self.getK(n)
m = (3 ** k - 1) / 2
if m != n:
self.reverse(start + m, start + n - 1)
self.reverse(start + n, start + n + m - 1)
self.reverse(start + m, start + n + m - 1)

for k in xrange(1, k + 1):
i = cursor = 3 ** (k - 1)
pre, visited = self.nums[i + start - 1], False
while not (i == cursor and visited):
i = (2 * i) % (2 * m + 1)
self.nums[i + start - 1], pre = pre, self.nums[i + start - 1]

if not visited:
visited = True

if n != m:
self.shuffle(start + 2 * m, end)

def wiggleSort(self, nums):
length = len(nums)
if length < 2:
return

nums.sort()

start, end = 1, length - 1
if not length & 1:
end -= 1

self.nums = nums
self.shuffle(start, end)
``````

• Nice in place solution~

• Is sorting necessarily O(1) in space? Quick sort is O(n) space and I can't think of anything that is better that also achieves O(nlogn) time

• It can be. For quicksort, see here.
For mergesort, see here

Therefore it depends on the library implement. For the purpose of this problem I think you may assume the sort used `O(1)` extra space.

• Interesting ... I can't view the article other than the abstract. Is wikipedia wrong then? https://en.wikipedia.org/wiki/Quicksort#Space_complexity

• Maybe the wikipedia writer just considered the classical variants of these sorting algorithms.
Then again, you may change the article yourself.
Anyway, for this problem sort is not always needed.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.