Common Algorithms
Merge Sort
Merge sort divides an array into smaller pieces, sorts those pieces, and merges the sorted pieces back together. The divide-and-conquer structure gives predictable O(n log n) performance.
Basic Implementation
Basic.java
import java.util.Arrays;
public class Basic {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
public static void main(String[] args) {
int[] numbers = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Before: " + Arrays.toString(numbers));
mergeSort(numbers, 0, numbers.length - 1);
System.out.println("After: " + Arrays.toString(numbers));
}
}
Divide and Conquer
A problem-solving strategy that breaks a problem into smaller subproblems, solves them independently, and combines the results.
Tracing the Algorithm
The trace shows the recursive divide phase followed by the merge phase.
Trace.java
import java.util.Arrays;
public class Trace {
private static int depth = 0;
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
indent();
System.out.println("Divide: " + arrayRange(arr, left, right));
depth++;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
depth--;
indent();
System.out.println("Merged: " + arrayRange(arr, left, right));
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
indent();
System.out.println(" Merge " + Arrays.toString(leftArr) +
" and " + Arrays.toString(rightArr));
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
private static void indent() {
for (int i = 0; i < depth; i++) System.out.print(" ");
}
private static String arrayRange(int[] arr, int left, int right) {
int[] range = new int[right - left + 1];
for (int i = 0; i < range.length; i++)
range[i] = arr[left + i];
return Arrays.toString(range);
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + Arrays.toString(numbers));
System.out.println();
mergeSort(numbers, 0, numbers.length - 1);
System.out.println();
System.out.println("Final: " + Arrays.toString(numbers));
}
}
import java.util.Arrays;
public class Trace {
private static int depth = 0;
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
indent();
System.out.println("Divide: " + arrayRange(arr, left, right));
depth++;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
depth--;
indent();
System.out.println("Merged: " + arrayRange(arr, left, right));
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
indent();
System.out.println(" Merge " + Arrays.toString(leftArr) +
" and " + Arrays.toString(rightArr));
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
private static void indent() {
for (int i = 0; i < depth; i++) System.out.print(" ");
}
private static String arrayRange(int[] arr, int left, int right) {
int[] range = new int[right - left + 1];
for (int i = 0; i < range.length; i++)
range[i] = arr[left + i];
return Arrays.toString(range);
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + Arrays.toString(numbers));
System.out.println();
mergeSort(numbers, 0, numbers.length - 1);
System.out.println();
System.out.println("Final: " + Arrays.toString(numbers));
}
}
import java.util.Arrays;
public class Trace {
private static int depth = 0;
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
indent();
System.out.println("Divide: " + arrayRange(arr, left, right));
depth++;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
depth--;
indent();
System.out.println("Merged: " + arrayRange(arr, left, right));
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
indent();
System.out.println(" Merge " + Arrays.toString(leftArr) +
" and " + Arrays.toString(rightArr));
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
private static void indent() {
for (int i = 0; i < depth; i++) System.out.print(" ");
}
private static String arrayRange(int[] arr, int left, int right) {
int[] range = new int[right - left + 1];
for (int i = 0; i < range.length; i++)
range[i] = arr[left + i];
return Arrays.toString(range);
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + Arrays.toString(numbers));
System.out.println();
mergeSort(numbers, 0, numbers.length - 1);
System.out.println();
System.out.println("Final: " + Arrays.toString(numbers));
}
}
The Merge Operation
MergeOnly.java
import java.util.Arrays;
public class MergeOnly {
public static int[] mergeTwoSorted(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
return result;
}
public static void main(String[] args) {
int[] left = {1, 3, 5, 7};
int[] right = {2, 4, 6, 8};
System.out.println("Left: " + Arrays.toString(left));
System.out.println("Right: " + Arrays.toString(right));
int[] merged = mergeTwoSorted(left, right);
System.out.println("Merged: " + Arrays.toString(merged));
int[] arr1 = {1, 5, 9};
int[] arr2 = {2, 3, 4, 6, 7};
System.out.println("\nLeft: " + Arrays.toString(arr1));
System.out.println("Right: " + Arrays.toString(arr2));
int[] merged2 = mergeTwoSorted(arr1, arr2);
System.out.println("Merged: " + Arrays.toString(merged2));
}
}
Merge Operation
The step that combines two sorted arrays into one sorted array by comparing the front values of each input.
Iterative Version
Bottom-up merge sort starts with runs of size one and repeatedly merges larger adjacent runs.
Iterative.java
import java.util.Arrays;
public class Iterative {
public static void mergeSortIterative(int[] arr) {
int n = arr.length;
for (int size = 1; size < n; size = size * 2) {
for (int left = 0; left < n - 1; left += size * 2) {
int mid = Math.min(left + size - 1, n - 1);
int right = Math.min(left + size * 2 - 1, n - 1);
merge(arr, left, mid, right);
}
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
public static void main(String[] args) {
int[] numbers = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Before: " + Arrays.toString(numbers));
mergeSortIterative(numbers);
System.out.println("After: " + Arrays.toString(numbers));
}
}
Practical Use
Merge sort is useful when stable, predictable sorting matters.
Practical.java
import java.util.Arrays;
class Student {
String name;
int score;
Student(String name, int score) {
this.name = name;
this.score = score;
}
public String toString() {
return name + ":" + score;
}
}
public class Practical {
public static void mergeSort(Student[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(Student[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
Student[] leftArr = new Student[n1];
Student[] rightArr = new Student[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i].score >= rightArr[j].score) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
public static void main(String[] args) {
Student[] students = {
new Student("Alice", 85),
new Student("Bob", 92),
new Student("Charlie", 78),
new Student("Diana", 95),
new Student("Eve", 88)
};
System.out.println("Before: " + Arrays.toString(students));
mergeSort(students, 0, students.length - 1);
System.out.println("After: " + Arrays.toString(students));
System.out.println("\nTop 3 students:");
for (int i = 0; i < 3 && i < students.length; i++) {
System.out.println((i + 1) + ". " + students[i]);
}
}
}
Exercise: Practical.java
Implement a merge function that counts the number of inversions while merging