Merge Sort | Most Optimized
 # Intuition  \n\n\n\n\n\n# Complexity\n- Time complexity: O(n * log(n))\n\n\n- Space complexity: O(n)\n\n\n# Code\n\nvoid merge(int arr[], int l, int r, int mi
<!-- # Intuition -->\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n<!-- # Approach -->\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n * log(n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nvoid merge(int arr[], int l, int r, int mid) {      /* DR167937-ag255126-01 -> */\n    int lsize = mid - l + 1, rsize = r - mid;\n    int left[lsize];\n    int i, j, k;\n    int *right = arr + mid + 1;\n    for(i = 0; i < lsize; i++)\n        left[i] = arr[l + i];\n    i = 0, j = 0, k = l;\n    while(i < lsize && j < rsize) {\n        if(left[i] < right[j])\n            arr[k++] = left[i++];\n        else\n            arr[k++] = right[j++];\n    }\n    while(i < lsize)\n        arr[k++] = left[i++];\n    while(j < rsize)\n        arr[k++] = right[j++];\n}\nvoid mergesort(int arr[], int l, int r) {\n    if(l < r) {\n        int mid = l + (r - l) / 2;\n        mergesort(arr, l, mid);\n        mergesort(arr, mid + 1, r);\n        merge(arr, l, r, mid);\n    }\n}       /* <- DR167937-ag255126-01 -> */\nint* sortArray(int* nums, int numsSize, int* returnSize){\n    mergesort(nums, 0, numsSize - 1);\n    *returnSize = numsSize;\n    return nums;\n}\n```
['Array', 'C', 'Merge Sort']