Merge Sort

Merge sort is an O(nlogn) runtime sorting algorithm. O(nlogn) is the fastest sorting time when sorting comparable objects. Merge sort is a divide and conquer algorithm since it breaks down the problem into smaller subproblems and solves the larger problem that way.

Algorithm:

1. Divide the list into the smallest unit (1 element)
2. Compare each element with the adjacent list
3. Sort and merge the two adjacent lists.

All the elements are sorted and merged:

Before proceeding to the code try to implement the algorithm on your own.

Solution (in java):

public class MergeSort {
    public static void main(String[] args) {
        // input array
        int[] arr = {2, 6, 3, 9, 7, 5, 1, 4, 8};

        // Call merge sort
        mergeSort(arr);

        // Check the output (should be sorted)
        System.out.println(java.util.Arrays.toString(arr));
    }

    public static int[] mergeSort(int[] list) {
        // do nothing if list is empty
        if (list.length <= 1) {
            return list;
        }

        // Create 2 lists to hold 1st and 2nd half of the list
        int[] first = new int[list.length / 2];
        int[] second = new int[list.length - first.length];
        // Split the array in half and populate above lists
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);

        // Sort each half recursively
        mergeSort(first);
        mergeSort(second);

        // Merge both halves together
        merge(first, second, list);
        return list;
    }

    private static void merge(int[] first, int[] second, int[] result) {
        // Index Position in first array - starting with first element
        int iFirst = 0;

        // Index Position in second array - starting with first element
        int iSecond = 0;

        // Index Position in merged array - starting with first position
        int iMerged = 0;

        // Compare elements at iFirst and iSecond,
        // and move smaller element at iMerged
        while (iFirst < first.length && iSecond < second.length) {
            if (first[iFirst] < second[iSecond]) {
                result[iMerged] = first[iFirst];
                iFirst++;
            } else {
                result[iMerged] = second[iSecond];
                iSecond++;
            }
            iMerged++;
        }
        // copy remaining elements from both halves
        System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
        System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
    }
}

output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Recursion can be tricky, so as you follow along make sure to have paper and pencil to draw down each step.

Clarifications:

The function arraycopy lies in the System class. It copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array:

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

Parameters:

• src − The source array
• srcPos − The starting position in the source array
• dest − The destination array
• destPos − The starting position in the destination data
• length − The number of array elements to be copied