Merge Sort

O(n log n)
n = size(array)

Python | Java

	def msort(nums: List[int]) -> None:
	def msort_helper(nums: List[int], l: int, r: int) -> None:
	if l >= r: return
	m = (l + r) // 2
	msort_helper(nums, l, m)
	msort_helper(nums, m + 1, r)
	merge(nums, l, r)
	def merge(nums: List[int], l: int, r: int) -> None:
	m = (l + r) // 2
	i, j = l, m + 1
	list = []
	for k in range(r - l + 1):
	if j > r or (i <= m and nums[i] < nums[j]):
	list.append(nums[i])
	i += 1
	else:
	list.append(nums[j])
	j += 1
	for k in range(len(list)):
	nums[l] = list[k]
	l += 1
	msort_helper(nums, 0, len(nums) - 1)

view raw MergeSort.py hosted with ❤ by GitHub

	void msort(int[] nums) {
	msort(nums, 0, nums.length - 1);
	}
	void msort(int[] nums, int l, int r) {
	if (l >= r) return;
	int m = (l + r) / 2;
	msort(nums, l, m);
	msort(nums, m + 1, r);
	merge(nums, l, r);
	}
	void merge(int[] nums, int l, int r) {
	int m = (l + r) / 2, i = l, j = m + 1;
	int[] arr = new int[r - l + 1];
	for (int k = 0; k < arr.length; k++) {
	if (j > r || (i <= m && nums[i] < nums[j])) arr[k] = nums[i++];
	else arr[k] = nums[j++];
	}
	for (int k = 0; k < arr.length; k++) {
	nums[l++] = arr[k];
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub