Merge Sort
Divide the sequence to be sorted into several subsequences. First, sort each subsequence individually. Once all subsequences are ordered, merge them together to form a single fully ordered sequence.
- Allocate space with a size equal to the sum of the two already sorted sequences; this space is used to store the merged result.
- Initialize two pointers at the starting positions of the two already sorted sequences.
- Compare the elements pointed to by the two pointers and select the smaller element to place into the merge buffer, then advance both pointers to their next positions.
- Repeat step 3 until one pointer reaches the end of its sequence.
- Copy all remaining elements from the other sequence directly into the tail of the merged sequence.
Code Implementation
::: code-tabs
@tab Java
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Make a copy of arr to avoid modifying the original parameter content
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
// Allocate result array with combined length of both input arrays
int[] result = new int[left.length + right.length];
int i = 0;
// Merge elements from both sorted subarrays into the result array
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
// Copy remaining elements from the left subarray if any exist
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
// Copy remaining elements from the right subarray if any exist
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
@tab JavaScript
function mergeSort(arr) { // Uses top-down recursive approach
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
// Recursively sort subarrays and merge the results
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
// Continue merging while both arrays have elements remaining
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
// Append any remaining elements from the left array
while (left.length) {
result.push(left.shift());
}
// Append any remaining elements from the right array
while (right.length) {
result.push(right.shift());
}
return result;
}
@tab Python
def merge_sort(arr): # Uses top-down recursive approach
if len(arr) < 2:
return arr
middle = int(len(arr) / 2)
left = arr[:middle]
right = arr[middle:]
# Recursively sort subarrays and merge the results
return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
result = []
# Continue merging while both arrays have elements remaining
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
# Append any remaining elements from the left array
result.extend(left)
# Append any remaining elements from the right array
result.extend(right)
return result
# The above code structure demonstrates the logic, though a more idiomatic Python implementation would typically use slicing and recursion without explicit popping for better performance.
@tab Go
func mergeSort(arr []int) (result []int, err error) { // Uses top-down recursive approach
if len(arr) < 2 {
return arr, nil
}
middle := int(len(arr) / 2)
left := make([]int, middle)
right := make([]int, len(arr)-middle)
copy(left, arr[:middle])
copy(right, arr[middle:])
// Recursively sort subarrays and merge the results
lRes, _ := mergeSort(left)
rRes, _ := mergeSort(right)
return merge(lRes, rRes), nil
}
func merge(left []int, right []int) (result []int) {
result = make([]int, len(left)+len(right))
i, j, k := 0, 0, 0
// Continue merging while both arrays have elements remaining
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
result[k] = left[i]
i++
} else {
result[k] = right[j]
j++
}
k++
}
// Append any remaining elements from the left array
for i < len(left) {
result[k] = left[i]
i++
k++
}
// Append any remaining elements from the right array
for j < len(right) {
result[k] = right[j]
j++
k++
}
return result
}
// The above code structure demonstrates the logic. In production, you might want to handle errors more explicitly or use slices differently based on Go best practices.
@tab PHP
function mergeSort($arr) { // Uses top-down recursive approach
if (count($arr) < 2) {
return $arr;
}
$middle = floor(count($arr) / 2);
$left = array_slice($arr, 0, $middle);
$right = array_slice($arr, $middle);
// Recursively sort subarrays and merge the results
return merge(mergeSort($left), mergeSort($right));
}
function merge($left, $right) {
$result = [];
// Continue merging while both arrays have elements remaining
while (!empty($left) && !empty($right)) {
if ($left[0] <= $right[0]) {
array_push($result, array_shift($left));
} else {
array_push($result, array_shift($right));
}
}
// Append any remaining elements from the left array
while (!empty($left)) {
array_push($result, array_shift($left));
}
// Append any remaining elements from the right array
while (!empty($right)) {
array_push($result, array_shift($right));
}
return $result;
}
// The above code structure demonstrates the logic. In production, consider using iterators or more efficient data structures if performance becomes critical with large datasets.