Given an array containing special characters, numbers, lowercase letters, and uppercase letters, write Python code to sort it so that special characters come first, followed by numbers, then lowercase letters, and finally uppercase letters.

Define a custom key that maps each element to a tuple representing its category and its natural order. For example, assign 0 to special characters, 1 to digits, 2 to lowercase letters, and 3 to uppercase letters. Use Python's sorted with this key. The key function can be:

import string
special = set(string.punctuation)

def sort_key(ch):
    if ch in special:
        return (0, ch)
    if ch.isdigit():
        return (1, ch)
    if ch.islower():
        return (2, ch)
    if ch.isupper():
        return (3, ch)
    return (4, ch)  # fallback

Then sort:

arr = ['b', '1', '@', 'A', 'c', '2', '#']
sorted_arr = sorted(arr, key=sort_key)

The algorithm runs in O(n log n) time due to the sort and uses O(n) additional space for the sorted list. It preserves the relative order within each category because the secondary key is the element itself.