Blog Logo
·
· · ·

### Merge Sort

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Time Complexity: $O(n\,log\,n)$

### Pseudocode

Merge(A, p, q, r):
n1 = p - q + 1
n2 = r - q
L = arr[n1]
R = arr[n2]
for k = 1 to n1:
L[k] = A[p + k - 1]
for k = 1 to n2:
R[k] = A[q + k]
i = 1
j = 1
for k = p to r:
if L[i] <= R[j]:
A[k] = L[i]
i++
else
A[k] = R[j]
j++


### Java Code


public class MergeSort {

public static int[] merge(int[] arr_l, int[] arr_r) {

int[] arr = new int[arr_l.length + arr_r.length];
int k;
int l = 0;
int r = 0;
for(k = 0; k < arr.length; k++) {
if(arr_l[l] <= arr_r[r]) {
arr[k] = arr_l[l];
l++;
} else {
arr[k] = arr_r[r];
r++;
}
if(l==arr_l.length || r==arr_r.length) {
k++;
break;
}
}

for(int j = l; j < arr_l.length; j++) {
arr[k] = arr_l[j];
k++;
}
for(int j = r; j < arr_r.length; j++) {
arr[k] = arr_r[j];
k++;
}

return arr;

}

public static int[] merge_sort(int[] arr) {

if(arr.length == 1) return arr;

int mid = (int) arr.length/2;

int left = mid;
int[] arr_l = new int[left];
for(int k = 0; k < left; k++) arr_l[k] = arr[k];

int right = arr.length-mid;
int[] arr_r = new int[right];
for(int k = 0; k < right; k++) arr_r[k] = arr[mid+k];

arr_l = merge_sort(arr_l);
arr_r = merge_sort(arr_r);
arr = merge(arr_l, arr_r);

return arr;

}

public static void print_arr(int[] arr) {

for(int i: arr) {
System.out.printf("%d ", i);
}
System.out.println("\n");

}

public static void main(String[] args) {

int[] arr = {1, 9, 8, 7, 6, 10, 5, 9};
MergeSort.print_arr(MergeSort.merge_sort(arr));

}

}



### Java Code for Inplace Merge Sort


public class MergeSortInplace {

static int[] arr;

public static void merge(int start, int mid, int end) {

int[] aux_arr = new int[end-start+1];
int k;

for(k = 0; k < end-start+1; k++) {
aux_arr[k] = arr[start + k];
}

k=start;
int i = 0;
int j = mid-start+1;

while(i <= mid-start && j <= end-start) {
if(aux_arr[i] <= aux_arr[j]) {
arr[k] = aux_arr[i];
i++;
} else {
arr[k] = aux_arr[j];
j++;
}
k++;
}

while(i<= mid-start) {
arr[k] = aux_arr[i];
i++;
k++;
}

while(j<=end-start) {
arr[k] = aux_arr[j];
j++;
k++;
}

}

public static void merge_sort(int start, int end) {

if(start >= end) return;
int mid = start + (end-start)/2;
merge_sort(start, mid);
merge_sort(mid+1, end);
merge(start, mid, end);

}

public static void print_arr(int[] arr) {

for(int i: arr) System.out.printf("%d ", i);
System.out.println();

}

public static void main(String[] args) {

int[] arr = {1, 3, 2, 5, 4, 7, 6, 10, 5, 8, 9};
MergeSortInplace.arr = arr;
merge_sort(0, MergeSortInplace.arr.length-1);
print_arr(MergeSortInplace.arr);

}

}



· · ·