Table of Contents
Merge sort Algorithm
Merge sort is a type of sorting algorithm that uses a divide–and–conquer approach to sort an array of items. It works by breaking the array down into smaller subarrays and then merging them back together in a specific order to produce a sorted array.
The process of breaking the array down into subarrays is repeated until each subarray consists of a single element, which is the base case for the algorithm.
The merge step then combines the subarrays together in a specific order to produce the sorted array. In essence, merge sort is a combination of two techniques: divide and conquer, and merging.
Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. It works by dividing an array into two halves, sorting each half, and then merging the sorted halves back together.
pseudocode
function mergeSort(array)
if length of array <= 1
return array
else
middle = length of array / 2
left = first half of array
right = second half of array
left = mergeSort(left)
right = mergeSort(right)
return merge(left, right)
function merge(left, right)
result = empty array
while left and right are both non-empty
if first element of left is less than or equal to first element of right
append first element of left to result
remove first element of left
else
append first element of right to result
remove first element of right
while left is non-empty
append first element of left to result
remove first element of left
while right is non-empty
append first element of right to result
remove first element of right
return result
Merge Sort Step by step Explanation
1. Divide the input array into two halves.
We will use the divide-and-conquer approach to divide the array into two halves. This means we will use a recursive approach to divide the array into two halves until it is broken down into individual elements.
2. Recursively sort each half.
We will use the same approach to recursively sort each half of the array. This means we will apply the same divide-and-conquer approach to each half until the array is broken down into individual elements.
3. Merge the sorted halves into one sorted array.
We will use the merge procedure to combine the two sorted halves into one sorted array. The merging step will involve comparing the elements of each half, and then adding them to the sorted array in the correct order.
4. Return the sorted array.
Finally, we will return the sorted array. This will be the final, sorted array that we have created.
The time complexity of merge sort is O(n*log(n)), making it more efficient than many other sorting algorithms, such as bubble sort and insertion sort. It is also a stable sort, meaning that the order of elements that compare as equal will be preserved.
Merge Sort Code in Multiple Language
C++
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& array, vector<int>& left, vector<int>& right) {
int i = 0, j = 0, k = 0;
while (i < left.size() && j < right.size()) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
} else {
array[k] = right[j];
j++;
}
k++;
}
while (i < left.size()) {
array[k] = left[i];
i++;
k++;
}
while (j < right.size()) {
array[k] = right[j];
j++;
k++;
}
}
void mergeSort(vector<int>& array) {
if (array.size() <= 1) {
return;
}
int middle = array.size() / 2;
vector<int> left(array.begin(), array.begin() + middle);
vector<int> right(array.begin() + middle, array.end());
mergeSort(left);
mergeSort(right);
merge(array, left, right);
}
int main() {
vector<int> array = {4, 2, 6, 1, 3, 5};
mergeSort(array);
for (int i : array) {
cout << i << " ";
}
cout << endl;
return 0;
}
Python
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left[0])
left.pop(0)
else:
result.append(right[0])
right.pop(0)
while left:
result.append(left[0])
left.pop(0)
while right:
result.append(right[0])
right.pop(0)
return result
def merge_sort(array):
if len(array) <= 1:
return array
middle = len(array) // 2
left = array[:middle]
right = array[middle:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
array = [4, 2, 6, 1, 3, 5]
sorted_array = merge_sort(array)
print(sorted_array)
JavaScript
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}
function mergeSort(array) {
if (array.length <= 1) {
return array;
}
let middle = Math.floor(array.length / 2);
let left = array.slice(0, middle);
let right = array.slice(middle);
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
let array = [4, 2, 6, 1, 3, 5];
let sortedArray = mergeSort(array);
console.log(sortedArray);
PHP
<?php
function merge($left, $right) {
$result = [];
while (count($left) && count($right)) {
if ($left[0] <= $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
while (count($left)) {
$result[] = array_shift($left);
}
while (count($right)) {
$result[] = array_shift($right);
}
return $result;
}
function mergeSort($array) {
if (count($array) <= 1) {
return $array;
}
$middle = count($array) / 2;
$left = array_slice($array, 0, $middle);
$right = array_slice($array, $middle);
$left = mergeSort($left);
$right = mergeSort($right);
return merge($left, $right);
}
$array = [4, 2, 6, 1, 3, 5];
$sortedArray = mergeSort($array);
print_r($sortedArray);
Java
import java.util.Arrays;
public class MergeSort {
public static void merge(int[] array, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
} else {
array[k] = right[j];
j++;
}
k++;
}
while (i < left.length) {
array[k] = left[i];
i++;
k++;
}
while (j < right.length) {
array[k] = right[j];
j++;
k++;
}
}
public static void mergeSort(int[] array) {
if (array.length <= 1) {
return;
}
int middle = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, middle);
int[] right = Arrays.copyOfRange(array, middle, array.length);
mergeSort(left);
mergeSort(right);
merge(array, left, right);
}
public static void main(String[] args) {
int[] array = {4, 2, 6, 1, 3, 5};
mergeSort(array);
System.out.println(Arrays.toString(array));
}
}
Insertion sort: a Sorting Algorithm
