1. Introduction

Merge Sort is a divide-and-conquer algorithm that divides the unsorted list into n sub-lists, each containing one element (a list with one element is considered sorted). Then, it repeatedly merges these sub-lists to produce new sorted sub-lists until there is only one sub-list remaining.

2. Program Steps

1. If the list has only one element, it is already sorted. Return it.

2. Divide the unsorted list into two sub-lists of about half the size.

3. Recursively sort both sub-lists.

4. Merge (combine) the two sorted sub-lists to produce one sorted list.

3. Code Program

public class MergeSort {

    // Merge two sorted sub-arrays of arr[].
    // First sub-array is arr[l..m]
    // Second sub-array is arr[m+1..r]
    public static void merge(int[] arr, int l, int m, int r) {
        // Find sizes of the two sub-arrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        // Create temp arrays to hold the values
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays L[] and R[]
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        // Merge the temp arrays back into arr[l..r]

        // Initial indexes of first and second sub-arrays
        int i = 0, j = 0;

        // Initial index of merged sub-array
        int k = l;

        // Merge the temp arrays while preserving order
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy the remaining elements of L[], if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy the remaining elements of R[], if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using merge()
    public static void sort(int[] arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = l + (r - l) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    // Driver method
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        // Call sort method to sort the array
        sort(arr, 0, arr.length - 1);

        // Print the sorted array
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array:
3 9 10 27 38 43 82

4. Step By Step Explanation

1. The merge function takes an array arr and three integers l, m, and r as arguments. This function is used to merge two halves of the array.

2. Within the merge function, two temporary arrays L[] and R[] are created to hold the two halves.

3. We then copy the two halves of arr[] to L[] and R[].

4. The two halves are then merged back into the original arr[] while ensuring that the array remains sorted.

5. The sort function recursively divides the array until each sub-array contains a single element.

6. After dividing the array, the sort function invokes the merge function to combine the sub-arrays in a sorted manner.

7. The main method initializes an unsorted array, invokes the sort method to sort the array, and then prints the sorted array.

The Merge Sort algorithm is efficient, having a time complexity of O(n log n) for all cases, making it more efficient than algorithms like Bubble, Insertion, and Selection Sort for larger lists. It's also a stable sort.