text: def swap(array, a, b):
      array[a], array[b] = array[b], array[a]
  
  class MaxHeapSort:
      @staticmethod
      def siftDown(array, root, dist, a):
          while root <= dist // 2:
              leaf = 2 * root
  
              if leaf < dist and array[a + leaf - 1] < array[a + leaf]:
                  leaf += 1
  
              if array[a + root - 1] < array[a + leaf - 1]:
                  swap(array, a + root - 1, a + leaf - 1)
                  root = leaf
              else: break
  
      @staticmethod
      def heapify(array, a, b):
          length = (b - a) // 2
  
          for i in range(length, 1, -1):
              MaxHeapSort.siftDown(array, i, length, a)
  
      @staticmethod
      def sort(array, a, b):
          MaxHeapSort.heapify(array, a, b)
  
          for i in range(b - a, 2, -1):
              swap(array, a, a + i - 1)
              MaxHeapSort.siftDown(array, 1, i - 1, a)
  
  class PDQSort:
      insertSortThreshold    = 24
      nintherThreshold       = 128
      partialInsertSortLimit = 8
  
      @staticmethod
      def pdqLog(n):
          n >>= 1
          log = 0
          while n != 0:
              log += 1
              n >>= 1
          return n
  
      @staticmethod
      def insertSort(array, a, b):
          if a == b: return
  
          for i in range(a + 1, b):
              if array[i] < array[i - 1]:
                  tmp = array[i]
  
                  j = i - 1
                  while array[j] > tmp and j >= a:
                      array[j + 1] = array[j]
                      j -= 1
                  array[j + 1] = tmp
  
      @staticmethod
      def unguardInsertSort(array, a, b):
          if a == b: return
  
          for i in range(a + 1, b):
              if array[i] < array[i - 1]:
                  tmp = array[i]
  
                  j = i - 1
                  while array[j] > tmp:
                      array[j + 1] = array[j]
                      j -= 1
                  array[j + 1] = tmp
  
      @staticmethod
      def partialInsertSort(array, a, b):
          if a == b: return
  
          limit = 0
          for i in range(a + 1, b):
              if limit > PDQSort.partialInsertSortLimit: return False
  
              if array[i] < array[i - 1]:
                  tmp = array[i]
  
                  j = i - 1
                  while array[j] > tmp and j >= a:
                      array[j + 1] = array[j]
                      j -= 1
                  array[j + 1] = tmp
  
              limit += i - j + 1
  
          return True
  
      @staticmethod 
      def sortTwo(array, a, b):
          if array[b] < array[a]:
              swap(array, a, b)
  
      @staticmethod
      def sortThree(array, a, b, c):
          PDQSort.sortTwo(array, a, b)
          PDQSort.sortTwo(array, b, c)
          PDQSort.sortTwo(array, a, b)
  
      @staticmethod
      def partRight(array, a, b):
          pivot = array[a]
  
          first = a
          last  = b
  
          while True:
              first += 1
              if not (array[first] < pivot): break
  
          if first - 1 == a:
              while True:
                  if not (first < last): break
                  last -= 1
                  if array[last] < pivot: break
          else:
              while True:
                  last -= 1
                  if array[last] < pivot: break
  
          alreadyParted = first >= last
  
          while first < last:
              swap(array, first, last)
  
              first += 1
              while array[first] < pivot:
                  first += 1
  
              last -= 1
              while not (array[last] < pivot):
                  last -= 1
  
          pivotPos = first - 1
          array[a] = array[pivotPos]
          array[pivotPos] = pivot
  
          return pivotPos, alreadyParted
  
      @staticmethod
      def partLeft(array, a, b):
          pivot = array[a]
  
          first = a
          last  = b
  
          while True:
              last -= 1
              if not (pivot < array[last]): break
  
          if last + 1 == b:
              while True:
                  if not (first < last): break
                  first += 1
                  if pivot < array[first]: break
          else:
              while True:
                  first += 1
                  if pivot < array[first]: break
  
          while first < last:
              swap(array, first, last)
  
              last -= 1
              while pivot < array[last]:
                  last -= 1
  
              first += 1
              while not (pivot < array[first]):
                  first += 1
  
          pivotPos = last
          array[a] = array[pivotPos]
          array[pivotPos] = pivot
  
          return pivotPos
  
      @staticmethod
      def pdqLoop(array, a, b, badAllowed):
          leftmost = True
  
          while True:
              size = b - a
  
              if size < PDQSort.insertSortThreshold:
                  if leftmost:
                      PDQSort.insertSort(array, a, b)
                  else:
                      PDQSort.unguardInsertSort(array, a, b)
                  return
  
              halfSize = size // 2
  
              if size > PDQSort.nintherThreshold:
                  PDQSort.sortThree(array, a, a + halfSize, b - 1)
                  PDQSort.sortThree(array, a + 1, a + (halfSize - 1), b - 2)
                  PDQSort.sortThree(array, a + 2, a + (halfSize + 1), b - 3)
                  PDQSort.sortThree(array, a + (halfSize - 1), a + halfSize, a + (halfSize + 1))
                  swap(array, a, a + halfSize)
              else:
                  PDQSort.sortThree(array, a, a + halfSize, b - 1)
  
              if (not leftmost) and (not array[a - 1] < array[a]):
                  a = PDQSort.partLeft(array, a, b) + 1
                  continue
  
              pivotPos, alreadyParted = PDQSort.partRight(array, a, b)
  
              leftSize  = pivotPos - a
              rightSize = b - (pivotPos + 1)
  
              highUnbalance = leftSize < size / 8 or rightSize < size / 8
  
              if highUnbalance:
                  badAllowed -= 1
                  if badAllowed == 0:
                      MaxHeapSort.sort(array, a, b)
                      return
  
                  if leftSize >= PDQSort.insertSortThreshold:
                      swap(array, a, a + leftSize // 4)
                      swap(array, pivotPos - 1, pivotPos - leftSize // 4)
  
                      if leftSize > PDQSort.nintherThreshold:
                          swap(array, a + 1, a + (leftSize // 4 + 1))
                          swap(array, a + 2, a + (leftSize // 4 + 2))
                          swap(array, pivotPos - 2, pivotPos - (leftSize // 4 + 1))
                          swap(array, pivotPos - 3, pivotPos - (leftSize // 4 + 2))
  
                  if rightSize >= PDQSort.insertSortThreshold:
                      swap(array, pivotPos + 1, pivotPos + (1 + rightSize // 4))
                      swap(array, b - 1, b - rightSize // 4)
  
                      if rightSize > PDQSort.nintherThreshold:
                          swap(array, pivotPos + 2, pivotPos + (2 + rightSize // 4))
                          swap(array, pivotPos + 3, pivotPos + (3 + rightSize // 4))
                          swap(array, b - 2, b - (1 + rightSize // 4))
                          swap(array, b - 3, b - (2 + rightSize // 4))
              elif (alreadyParted and PDQSort.partialInsertSort(array, a, pivotPos) 
                                  and PDQSort.partialInsertSort(array, pivotPos + 1, b)):
                  return
  
              PDQSort.pdqLoop(array, a, pivotPos, badAllowed)
              a = pivotPos + 1
              leftmost = False
  
  def pdqSort(array, a, b):
      PDQSort.pdqLoop(array, a, b, PDQSort.pdqLog(b - a))
  