Sort Strings

Given a list of strings, write a function, sorting from scratch to sort the list in ascending alphabetical order.

Notes: - Do NOT use the built-in sorted function - Return the new sorted list, rather than modifying the list in-place

Bonus: Have your solution be $O(n log(n))$.

Example:

Input:

array = ["apple", "cat", "banana", "zoo", "football"]

Output:

def sorting(array) -> ["apple", "banana", "cat", "football", "zoo"]