# Algorithm: Merge Sort # Type: Sorting, Divide and Conquer # Time Complexity: O(n log n) # Space Complexity: O(n) function mergeSort(arr): if length(arr) <= 1: return arr mid = length(arr) / 2 left = mergeSort(arr[0:mid]) right = mergeSort(arr[mid:]) return merge(left, right) function merge(left, right): result = [] while left and right: if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) return result + left + right