// Java

public static void mergeSort(int[] array, int left, int right) {

    if (right <= left) return;

    int mid = (left + right) >> 1; // (left + right) / 2

    mergeSort(array, left, mid);

    mergeSort(array, mid + 1, right);

    merge(array, left, mid, right);

}

public static void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[right - left + 1]; // 中间数组

        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {

            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];

        }

        while (i <= mid)   temp[k++] = arr[i++];

        while (j <= right) temp[k++] = arr[j++];

        for (int p = 0; p < temp.length; p++) {

            arr[left + p] = temp[p];

        }

        // 也可以用 System.arraycopy(a, start1, b, start2, length)

    }

C/C++

void mergeSort(vector<int> &nums, int left, int right) {

if (left >= right) return;

int mid = left + (right - left) / 2;

mergeSort(nums, left, mid);

mergeSort(nums, mid+1, right);

merge(nums, left, mid, right);

}

void merge(vector<int> &nums, int left, int mid, int right) {

vector<int> tmp(right-left+1);

int i = left, j = mid+1, k = 0;

while (i <= mid && j <= right) {

tmp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];

}

while (i <= mid) tmp[k++] = nums[i++];

while (j <= right) tmp[k++] = nums[j++];

for (i = left, k = 0; i <= right;) nums[i++] = tmp[k++];

}

#Python

def mergesort(nums, left, right):

if right <= left:

return

mid = (left+right) >> 1

mergesort(nums, left, mid)

mergesort(nums, mid+1, right)

merge(nums, left, mid, right)

def merge(nums, left, mid, right):

temp = []

i = left

j = mid+1

while i <= mid and j <= right:

if nums[i] <= nums[j]:

temp.append(nums[i])

i +=1

else:

temp.append(nums[j])

j +=1

while i<=mid:

temp.append(nums[i])

i +=1

while j<=right:

temp.append(nums[j])

j +=1

nums[left:right+1] = temp

// JavaScript

const mergeSort = (nums) => {

  if (nums.length <= 1) return nums

  let mid = Math.floor(nums.length/2), 

      left = nums.slice(0, mid), 

      right = nums.slice(mid)

  return merge(mergeSort(left), mergeSort(right))

}

const merge = (left, right) => {

  let result = []

  while(left.length && right.length) {

    result.push(left[0] <= right[0] ? left.shift() : right.shift())

  }

  while(left.length) result.push(left.shift())

  while(right.length) result.push(right.shift())

  return result

}