Merge Sort - LAB Assignment 1

SWE2009 – Analysis of Algorithms

PREPARED BY: Sai Sanjay 21MIC7178
Under the guidance of Prof.Manomita Chakraborty

---

Implement Merge Sort and Check the following cases:

Case 1: Take a sorted array of smaller Size and check the running time of the algorithm.

Case 2: Take an unsorted array of smaller Size and check the running time of the algorithm.

Case 3: Take a sorted array of larger Size and check the running time of the algorithm.

Case 4: Take an unsorted array of larger Size and check the running time of the algorithm.

Code :

package lab.mergesort;  
  
import java.util.Arrays;  
import java.util.Random;  
  
  
public class MergeSort {  
    public static void main(String[] args) {  
        testCase1();  
        testCase2();  
        testCase3();  
        testCase4();  
//        analyzeResults();  
    }  
  
    public static void testCase1() {  
        System.out.println("Case 1: Sorted array of smaller size");  
        int[] arr = {1, 2, 3, 4, 5};  
        runTest(arr);  
    }  
  
    public static void testCase2() {  
        System.out.println("Case 2: Unsorted array of smaller size");  
        int[] arr = {9, 5, 2, 8, 1};  
        runTest(arr);  
    }  
  
    public static void testCase3() {  
        System.out.println("Case 3: Sorted array of larger size");  
        int[] arr = new int[100000];  
        for (int i = 0; i < arr.length; i++) {  
            arr[i] = i;  
        }  
        runTest(arr);  
    }  
  
    public static void testCase4() {  
        System.out.println("Case 4: Unsorted array of larger size");  
        int[] arr = new int[100000];  
        Random rand = new Random();  
        for (int i = 0; i < arr.length; i++) {  
            arr[i] = rand.nextInt(1000000);  
        }  
        runTest(arr);  
    }  
  
    public static void runTest(int[] arr) {  
        int[] arrCopy = Arrays.copyOf(arr, arr.length);  
        long startTime = System.nanoTime();  
        mergeSort(arr, 0, arr.length - 1);  
        long endTime = System.nanoTime() - startTime;  
        System.out.println("Runtime: " + endTime + " ns");  
        System.out.println("Array sorted correctly: " + isSorted(arr));  
        System.out.println();  
    }  
  
    public static boolean isSorted(int[] arr) {  
        for (int i = 1; i < arr.length; i++) {  
            if (arr[i - 1] > arr[i]) {  
                return false;  
            }  
        }  
        return true;  
    }  
  
  
  
    public static 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++;  // This line was missing  
        }  
        while (i < n1) {  
            arr[k] = L[i];  
            i++;  
            k++;  
        }  
        while (j < n2) {  
            arr[k] = R[j];  
            j++;  
            k++;  
        }  
    }  
  
    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);  
        }  
    }  
}

Output :

What have you analyzed from all the results?

1. The merge sort algorithm has a time complexity of O(n log n) for all cases.
2. For smaller arrays, the difference in runtime between sorted and unsorted arrays is minimal.
3. For larger arrays, the algorithm takes significantly more time due to the increased number of elements.
4. The algorithm performs equally well for both sorted and unsorted arrays of the same size.
5. The efficiency of merge sort is evident in its ability to handle large datasets relatively quickly.