from typing import List
from typing import Any


def stable_sort(deck: List[Any]) -> List[Any]:
    """Sort of list of object, assuming that <, ==, and > are implement for the
    objects in the list.

    This function implements a merge sort, which has an average performance of
    O(nlog(n)) and a worst case performance of O(nlog(n)). Although merge sort
    can have memory usage of O(n), because Python requires passing by value and
    not by reference, this implementation uses O(nlog(n)) memory. This sort is
    stable so the order between identical objects in the input array is
    preserved.
    
    Arguments:
        deck: List[Any]
            List of objects to be sorted

    Returns:
        List[Any]: sorted list of objects
    """
    if len(deck) > 1:
        first = stable_sort(deck[:len(deck) // 2])
        last = stable_sort(deck[(len(deck) // 2):])
        i = 0
        j = 0
        while i < len(first) or j < len(last):
            if i >= len(first):
                deck[i + j] = last[j]
                j += 1
            elif j >= len(last):
                deck[i + j] = first[i]
                i += 1
            elif first[i] < last[j]:
                deck[i + j] = first[i]
                i += 1
            else:
                deck[i + j] = last[j]
                j += 1
    return deck