Merge Sort
Continue with Classes, Queues, performing Sorts and BigO analysis on your algorithm(s).
Merge Sort Simulation - Part 1: General Concept
Merge Sort is a divide and conquer algorithm that splits a list into smaller sublists, sorts those sublists, and then merges them back together to form the sorted list. It is particularly efficient for large datasets.
Steps of Merge Sort:
- Divide: Recursively split the list into two halves until each sublist contains a single element or is empty.
- Conquer: Sort each of the smaller sublists.
- Combine: Merge the sorted sublists back together to form the final sorted list.
Time Complexity of Merge Sort
Merge Sort has a predictable time complexity due to its divide-and-conquer approach. Here’s a breakdown:
-
Divide Step: The list is divided into two halves recursively. This takes O(n log n)time because the list is halved at each level of recursion.
-
Merge Step: At each level of recursion, the merging of two halves takes O(n) time, where n is the number of elements being merged.
-
Overall Complexity: Since there are O(log n) levels of recursion and each level takes O(n) time to merge, the total time complexity is: O(n log n)
Popcorn Hack
- Why do we divide the array into halves in Merge Sort?
- Why does Merge Sort have O(n log n) complexity?
Example Walk Through
public class MergeSort {
// Main function to sort an array
public static void mergeSort(int[] array) {
if (array.length < 2) {
return; // Base case: an array of length 0 or 1 is already sorted
}
// Find the middle index
int mid = array.length / 2;
// Divide the array into two halves
int[] left = new int[mid];
int[] right = new int[array.length - mid];
// Copy data to left and right subarrays
System.arraycopy(array, 0, left, 0, mid);
System.arraycopy(array, mid, right, 0, array.length - mid);
// Recursively sort both halves
mergeSort(left);
mergeSort(right);
// Merge the sorted halves
merge(array, left, right);
}
// Helper function to merge two sorted arrays
public static void merge(int[] array, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
// Merge the two sorted subarrays
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
} else {
array[k] = right[j];
j++;
}
k++;
}
// Copy the remaining elements of left[] if any
while (i < left.length) {
array[k] = left[i];
i++;
k++;
}
// Copy the remaining elements of right[] if any
while (j < right.length) {
array[k] = right[j];
j++;
k++;
}
}
// Main method to test the merge sort
public static void main(String[] args) {
int[] array = { 38, 27, 43, 3, 9, 82, 10 };
System.out.println("Original array:");
System.out.println(Arrays.toString(array));
mergeSort(array);
System.out.println("Sorted array:");
System.out.println(Arrays.toString(array));
}
}
Explanation of the Code:
mergeSortfunction:- This function is the main sorting function.
- If the array has only one element or is empty, it’s already sorted, and the function returns immediately.
- Otherwise, the array is split into two subarrays:
leftandright. - It recursively sorts each half using the same
mergeSortfunction.
mergefunction:- After both halves are sorted, we need to combine them back together in sorted order.
- It compares the elements of
leftandrightarrays, putting the smaller element into the mainarrayuntil one of the subarrays is exhausted. - After that, it copies any remaining elements from the
leftorrightarrays into the mainarray.
mainfunction:- This function tests the merge sort by creating an unsorted array, printing it, sorting it using
mergeSort, and then printing the sorted array.
- This function tests the merge sort by creating an unsorted array, printing it, sorting it using
Let’s say we have this array:
[38, 27, 43, 3, 9, 82, 10]
- Divide Step:
- Split into two parts:
Left: [38, 27, 43]
Right: [3, 9, 82, 10]
- Split into two parts:
- Recursion:
- Sort each half:
- Left: [38, 27, 43] → Split again into [38] and [27, 43] → Sort to [27, 38, 43]
- Right: [3, 9, 82, 10] → Split into [3, 9] and [82, 10] → Sort to [3, 9] and [10, 82]
- Sort each half:
- Merge Step:
- Now merge back:
- Merging [27, 38, 43] and [3, 9, 10, 82], results in the sorted array:
[3, 9, 10, 27, 38, 43, 82]
- Merging [27, 38, 43] and [3, 9, 10, 82], results in the sorted array:
- Now merge back:
class MergeSort {
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
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 sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
static void printArray(int arr[]) {
for (int i : arr)
System.out.print(i + " ");
System.out.println();
}
public static void main(String args[]) {
int arr[] = { 12, 11, 13, 5, 6, 7 };
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
}
MergeSort mergesort = new MergeSort();
mergesort.main(null);
Sorted array:
5 6 7 11 12 13
Popcorn hack modifications to this code
- ask class to modify the code to sort the array in decesnding order
- Ask students to count the number of comparisons happening in the merge() function and print the count.
- Write a Java method that checks if a given array is already sorted before applying Merge Sort.
class MergeSort {
private int comparisonCount = 0;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
comparisonCount++;
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 sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
static void printArray(int arr[]) {
for (int i : arr)
System.out.print(i + " ");
System.out.println();
}
boolean isSortedDescending(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < arr[i + 1]) {
return false;
}
}
return true;
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
MergeSort ob = new MergeSort();
if (ob.isSortedDescending(arr)) {
System.out.println("Array is already sorted in descending order.");
} else {
ob.sort(arr, 0, arr.length - 1);
System.out.println("Sorted array in descending order:");
printArray(arr);
System.out.println("Total comparisons: " + ob.comparisonCount);
}
}
}
MergeSort mergesort = new MergeSort();
mergesort.main(null);
Sorted array in descending order:
13 12 11 7 6 5
Total comparisons: 7
Homework
Task 1:
- Explain Merge Sort in Your Own Words Write a short explanation (100-200 words) describing: Merge sort uses a divide and conquer sorting algorithm to split the array into smaller arrays and then merges the arrays back together. It first divides into halves until each array is just one element. Then it conquers /merges all of the sorted small arrays leading to a sorted array. It has O(n log n) complexity as it splits it into halves taking log(n) levels of recursion before merging all n elements into the sorted arrays, leading to n log n Bubble sort has a time compleixty of n^2 and is generally slow. While quick sort is fast, it does have a bad time complexity of n^2. Merge sort is great for stability and performance
- How Merge Sort works.
- Why it has O(n log n) complexity.
- How it differs from other sorting algorithms like Bubble Sort or Quick Sort.
Task 2
- Code a Modified Version of Merge Sort Choose ONE of the following modifications and implement it in Java:
- Option A: Merge Sort Without Recursion
- Modify the Merge Sort algorithm to work iteratively instead of recursively.
- Option B: Counting Inversions Using Merge Sort
- Modify Merge Sort to count the number of inversions in an array. (An inversion is when a larger number appears before a smaller number in an array.)
- Option C: Sorting a Linked List Using Merge Sort
- Instead of an array, implement Merge Sort for a singly linked list.
Option C
class MergeSortLinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private int comparisonCount = 0;
Node getMiddle(Node head) {
if (head == null) return head;
Node slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Node merge(Node left, Node right) {
if (left == null) return right;
if (right == null) return left;
comparisonCount++;
Node result;
if (left.data >= right.data) {
result = left;
result.next = merge(left.next, right);
} else {
result = right;
result.next = merge(left, right.next);
}
return result;
}
// Main Merge Sort function
Node mergeSort(Node head) {
if (head == null || head.next == null)
return head;
Node middle = getMiddle(head);
Node nextOfMiddle = middle.next;
middle.next = null;
Node left = mergeSort(head);
Node right = mergeSort(nextOfMiddle);
return merge(left, right);
}
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
MergeSortLinkedList list = new MergeSortLinkedList();
Node head = new Node(12);
head.next = new Node(11);
head.next.next = new Node(13);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(6);
head.next.next.next.next.next = new Node(7);
System.out.println("Original list:");
list.printList(head);
head = list.mergeSort(head);
System.out.println("Sorted list in descending order:");
list.printList(head);
System.out.println("Total comparisons: " + list.comparisonCount);
}
}
MergeSortLinkedList linkSort = new MergeSortLinkedList();
linkSort.main(null);
Original list:
12 11 13 5 6 7
Sorted list in descending order:
13 12 11 7 6 5
Total comparisons: 7