Sort an Array of 0s, 1s and 2s

Problem Statement

Given an array arr[] containing only 0s, 1s, and 2s, sort the array in ascending order without using any built-in sort function.

Example 1:
Input: [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
Example 2:
Input: [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]

apporach

The optimal way to solve this problem is by using the Dutch National Flag Algorithm which works in a single pass and uses constant extra space.
We divide the array into three regions:

Left - all 0s
Middle - all 1s
Right - all 2s

To achieve this, we use three pointers:

low - position to place the next 0
mid - current element
high - position to place the next 2

Python Code
class Solution:
def sort012(self, arr):
low = 0
mid = 0
high = len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1

        elif arr[mid] == 1:
            mid += 1

        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

Conclusion

It is a example of optimizing both time and space complexity.