Merge Sort
An efficient and stable algorithm, based on divide and conquer paradigm.
Time Complexity
O(n log n)
NiceSpace Complexity
O(n)
GoodIn-Place
Yes
YesStability
Yes
YesDifficulty
Hard
★★★★☆Description
Merge Sort is a sorting algorithm based on the divide and conquer paradigm. The core idea is to recursively divide the array into two halves, sort each half, and then merge the two sorted halves.
The merging process is the fundamental part of the algorithm:
- Divide the array into two halves
- Recursively sort each half
- Merge the two sorted halves
This approach guarantees a time complexity of O(n log n) in all cases (best, average, and worst), making it highly efficient for large datasets.
Merge Sort is particularly useful when the data to be sorted does not fit entirely in main memory and must be handled using external memory (external sorting).
Computational Complexity
Implementation
PYTHON
C
C++
merge_sort.python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Esempio di utilizzo
arr = [12, 11, 13, 5, 6, 7]
print("Array originale:", arr)
merge_sort(arr)
print("Array ordinato:", arr)
merge_sort.c
#include
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Array originale: ");
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
mergeSort(arr, 0, arr_size - 1);
printf("\nArray ordinato: ");
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
return 0;
}
merge_sort.cpp
#include
#include
using namespace std;
void merge(vector& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
vector L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
vector arr = {12, 11, 13, 5, 6, 7};
cout << "Array originale: ";
for (int num : arr) cout << num << " ";
cout << endl;
mergeSort(arr, 0, arr.size() - 1);
cout << "Array ordinato: ";
for (int num : arr) cout << num << " ";
return 0;
}