Computer Science A

Course Progress 0/0
Sprint View
Week 20 Merge Sort

Merge Sort

5 min read

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:

  1. Divide: Recursively split the list into two halves until each sublist contains a single element or is empty.
  2. Conquer: Sort each of the smaller sublists.
  3. Combine: Merge the sorted sublists back together to form the final sorted list.

merge sort visual 1

merge sort visual 2

Merge Sort Big O

Let $n$ be the number of elements in the array.

Merge sort uses a divide-and-conquer approach, which gives it a predictable time complexity:

  • Divide step: The array is recursively split in half until each subarray contains a single element. This process takes $O(\log n)$ steps, since the array is halved at each level of recursion.
  • Merge step: At each level, merging all subarrays back together takes $O(n)$ time, since every element is processed at each level.

Total number of operations: $O(n \log n)$, since there are $O(\log n)$ levels and each level processes $n$ elements.

  • Best case: $O(n \log n)$ (array is already sorted, but merge sort still divides and merges all elements).

  • Average case: $O(n \log n)$ (random order).

  • Worst case: $O(n \log n)$ (reverse order or any order; merge sort always does the same number of operations regardless of input order).

Merge Sort

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:

  1. 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 and right.
    • It recursively sorts each half using the same mergeSort function.
  2. merge function:
    • After both halves are sorted, we need to combine them back together in sorted order.
    • It compares the elements of left and right arrays, putting the smaller element into the main array until one of the subarrays is exhausted.
    • After that, it copies any remaining elements from the left or right arrays into the main array.
  3. 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.

Let’s say we have this array:

[38, 27, 43, 3, 9, 82, 10]

  1. Divide Step:
    • Split into two parts:
      Left: [38, 27, 43]
      Right: [3, 9, 82, 10]
  2. 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]
  3. 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]
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);
    }
}

Course Timeline