class Quicksort:
    def __init__(self):
        self._data = None
        
    def sort(self, data):
        """
        Quicksort a list of data.
        """
        self._data = data
        self._sort(0, len(data) - 1)
        self._verify_sorted()
    
    def _sort(self, left, right):
        """
        Recursively sort a sublist.
        @param left the leftmost index of the sublist.
        @param right the rightmost index of the sublist.
        """
        size = right - left + 1

        # Size > 2: Partition and recursively
        #           sort the sublists.
        if size > 2:
            pivot_index = self._partition(left, right)

            # Recursively sort the left sublist.
            if left != pivot_index:
                self._sort(left, pivot_index - 1)

            # Recursively sort the right sublist.
            if right != pivot_index:
                self._sort(pivot_index + 1, right)

        # Size == 2: Swap if necessary.
        elif (size == 2) and (self._data[left] > self._data[right]):
            self._data[left], self._data[right] = \
                self._data[right], self._data[left]
    
    def _partition(self, left, right):
        """
        Partition the part of list data bounded by indexes 
        left and right.
        @param left the leftmost index of the sublist.
        @param right the rightmost index of the sublist.
        @return the final index of the pivot value.
        """
        # Pick the pivot value.
        middle = (left + right)//2
        pivot_value = self._data[middle]

        # Swap the pivot value with the rightmost value.
        self._data[middle], self._data[right] = \
            self._data[right], self._data[middle]

        i = left - 1
        j = right

        # As long as i and j don't cross ...
        while i < j:

            # Move i to the right.
            i += 1
            while (i < right) and (self._data[i] <= pivot_value):
                i += 1

            # Move j to the left.
            j -= 1
            while (j > left) and (self._data[j] > pivot_value):
                j -= 1

            # Swap after i and j have stopped moving.
            if (i < j) and (self._data[i] != self._data[j]):
                self._data[i], self._data[j] = \
                    self._data[j], self._data[i]

        # Swap the pivot value from the right end 
        # to its correct position.
        if self._data[i] != self._data[right]:
            self._data[i], self._data[right] = \
                self._data[right], self._data[i]
        
        return i

    def _verify_sorted(self):
        """
        Verify that the data list 
        has been successfully sorted.
        """
        for k in range(1, len(self._data)):
            value = self._data[k]
            prev  = self._data[k - 1]
            
            if value < prev:
                raise Exception('Sort error: '
                                f'{value} < {prev} at {k}')