class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        This is the Dutch National Flag partitioning algorithm (also known as three-way partitioning), famously used to sort an array containing only 0s, 1s, and 2s. Here's how it works in simple terms:

        The algorithm uses three pointers:
        left: tracks where we should put the next 0
        right: tracks where we should put the next 2
        index: current number we're looking at
        As we move through the array with index, we handle each number differently:
        - If we find a 0:
        Swap it with the number at the left pointer
        Move left one step right
        Move index forward
        - If we find a 2:
        Swap it with the number at the right pointer
        Move right one step left
        Don't move index (because we need to check the new number we just swapped in)
        - If we find a 1:
        Leave it where it is
        Just move index forward
        
        The process continues until index crosses right.
        For example, if you start with [2,0,1,2,1,0]:
        Initial: [2,0,1,2,1,0]  left=0, right=5
        Step 1:  [0,2,1,2,1,0]  (swap 2 and 0)
        Step 2:  [0,0,1,2,1,2]  (swap 2 and 0)
        Step 3:  [0,0,1,1,2,2]  (final swaps for 2s)
        """
        right = len(nums)-1
        left = 0
        index = 0
        while index <= right:
            if nums[index] == 0:
                temp = nums[left]
                nums[left] = 0
                nums[index] = temp
                left = left + 1
                index = index + 1
                continue
            if nums[index] == 2:
                temp = nums[index]
                nums[index] = nums[right]
                nums[right] = 2
                right = right - 1
                continue
            if nums[index] == 1:
                index = index + 1
                continue
        return nums
        """
        This is also an algorithm to sort an array of 0s, 1s, and 2s, but it takes a different approach using three separate passes through the array. Here's how it works:

        - First Pass (Swap 0s and 2s):
        From right: Look for 0s
        From left: Look for 2s
        When found, swap them This puts most 2s towards the left and 0s towards the right
        - Second Pass (Swap 0s and 1s):
        From right: Look for 0s
        From left: Look for 1s
        When found, swap them This moves 0s towards the left
        - Third Pass (Swap 1s and 2s):
        From right: Look for 1s
        From left: Look for 2s
        When found, swap them This puts 1s in the middle
        Each pass uses two pointers (left and right) that move towards each other, and swaps elements when they find a pair that needs to be exchanged.

        For example, with [2,0,1,2,1,0]:
        After first pass:  [0,0,1,2,1,2]  (swapped 0s and 2s)
        After second pass: [0,0,1,2,1,2]  (swapped 0s and 1s)
        After third pass:  [0,0,1,1,2,2]  (swapped 1s and 2s)
        While this algorithm also works, it's less efficient than the Dutch National Flag algorithm because:

        It makes three passes through the array instead of one
        It might do unnecessary swaps
        It has O(n) time complexity but with a larger constant factor
        The previous algorithm (Dutch National Flag) is generally preferred because it solves the problem in a single pass.
        """
        # right = len(nums)-1
        # left = 0
        # while right > left:
        #     if nums[right] != 0:
        #         right = right - 1 
        #         continue
        #     if nums[left] != 2:
        #         left = left + 1 
        #         continue
        #     temp = nums[left]
        #     nums[left] = nums[right]
        #     nums[right] = temp
        #     left = left + 1
        #     right = right - 1
        # right = len(nums) - 1
        # left = 0
        # while right > left:
        #     if nums[right] != 0:
        #         right = right - 1 
        #         continue
        #     if nums[left] != 1:
        #         left = left + 1 
        #         continue
        #     temp = nums[left]
        #     nums[left] = nums[right]
        #     nums[right] = temp
        #     left = left + 1
        #     right = right - 1
        # right = len(nums) - 1
        # left = 0
        # while right > left:
        #     if nums[right] != 1:
        #         right = right - 1 
        #         continue
        #     if nums[left] != 2:
        #         left = left + 1 
        #         continue
        #     temp = nums[left]
        #     nums[left] = nums[right]
        #     nums[right] = temp
        #     left = left + 1
        #     right = right - 1
        # return nums