overview
Divides the array into halves recursively, sorts each half, and merges them to achieve a sorted array.

time complexity
O(n log n)

Space complexity
O(n) - requires additional memory proportional to the array size