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:
mergeSort
function:- 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:
left
andright
. - It recursively sorts each half using the same
mergeSort
function.
merge
function:- After both halves are sorted, we need to combine them back together in sorted order.
- It compares the elements of
left
andright
arrays, putting the smaller element into the mainarray
until one of the subarrays is exhausted. - After that, it copies any remaining elements from the
left
orright
arrays into the mainarray
.
main
function:- 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);
}
}
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.
Homework
Task 1:
- Explain Merge Sort in Your Own Words Write a short explanation (100-200 words) describing:
- 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.