Sort an array of 0, 1, 2 and 3.

Problem: Sort an array which only contains 0, 1, 2 and 3

Example:

Input: arr = [0, 3, 1, 2, 0, 1, 3, 1, 2]
Output: [0, 0, 1, 1, 1, 2, 2, 3, 3]

Approach: The problem is similar to the problem of sorting an array containing only 0, 1 and 2. We will use the same approach which we took there. We will start with three pointers low, high and mid but here we want mid to have both 1 and 2 so our intermediate result would be something like:

0, 0, 0, ..., 0,  1, 2, 2, 1, 2, 1, 3, 3, 3, ... 3

Now we just need to sort the mid array which contains only 1 and 2. We can use the approach which we have taken to solve the problem of sorting array containing only 0 and 1.

Implementation in C#:

    private static void Sort0123(int[] arr)

    {

        int low = 0, mid = 0, high = arr.Length - 1;

        while (mid <= high)

        {

            switch(arr[mid])

            {

                case 0: 

                    Swap(arr, low, mid);

                    ++low;

                    ++mid;

                    break;

                case 1:

                case 2:

                    ++mid;

                    break;

                case 3:

                    Swap(arr, mid, high);

                    --high;

                    break;

                default:

                    break;

            }

        }

        while(low <= high)

        {

            if (arr[low] == 2)

            {

                Swap(arr, low, high);

                --high;

            }

            else

            {

                ++low;

            }

        }

        

    }

Complexity: O(n)