Sorting an Array of 0s, 1s and 2s Without Built-in Sort

Problem Statement:
Given an array containing only 0s, 1s, and 2s, sort the array in ascending order without using the built-in sort function.

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

Approach:
Since the array contains only three values, we can count the number of 0s, 1s, and 2s. After counting, we rewrite the array by placing all 0s first, then all 1s, and finally all 2s.

Code:

def sort012(arr):
count0 = 0
count1 = 0
count2 = 0

for num in arr:
    if num == 0:
        count0 += 1
    elif num == 1:
        count1 += 1
    else:
        count2 += 1

index = 0

for i in range(count0):
    arr[index] = 0
    index += 1

for i in range(count1):
    arr[index] = 1
    index += 1

for i in range(count2):
    arr[index] = 2
    index += 1

return arr

Explanation:
This method does not use any built-in sorting function. It works by counting each element and rebuilding the array in sorted order.

Time Complexity:
O(n), because we traverse the array and rewrite it.

Space Complexity:
O(1), because only a few extra variables are used.