Mergesort is a comparison sort, same as quicksort and based on divide and conquer algorithm. It divides the original data set into smaller pieces of data set to solve the problem and then finally merge these small data sets.

How Merge Sort Works

Merge sort works in the following way:

1. Merge sort, take middle index in data set and split into two collections : one collection for items left of middle index and second for right values of middle index.
2. Repeat step 1 as long as these collections size reach to one item only.
3. Now merge sort picks the items from smaller collections, sort them and merge to create new collection.
4. Repeat this sort and merge process until all small colection sort and merge not completed.
5. Finally will get single collection with sorted result.

Points to Remember

• Data Structure: Array
• Best Time Complexity: Ω(n log(n))
• Average Time Complexity: Θ(n log(n))
• Worst Time Complexity: O(n log(n))
• Worst Space Complexity: O(n)

Merge Sort Program

public class MergeSort {

    public int[] sort(int [] array){
     mergeSort(array, 0, array.length-1);
     return array;

    }

    private void mergeSort(int[] array, int first, int last) {

     // Get mid position to divide problem into smaller size collections
     int mid = (first + last) / 2;

     //If first < last the array must be recursively sorted
     if (first < last) {
      mergeSort(array, first, mid);
      mergeSort(array, mid + 1, last);
     }

     //merge solved collections to get solution to original problem
     int a = 0, f = first, l = mid + 1;
     int[] temp = new int[last - first + 1];

   //decide the swapping of items
     while (f <= mid && l <= last) {
      temp[a++] = array[f] < array[l] ? array[f++] : array[l++];
     }

     while (f <= mid) {
      temp[a++] = array[f++];
     }

     while (l <= last) {
      temp[a++] = array[l++];
     }

     a = 0;
     while (first <= last) {
      array[first++] = temp[a++];
     }
    }

    public static void printArray(int[] array) {
     for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
     }

    }

    public static void main(String[] args) {

     System.out.println("Original array before Merge sort");
     int[] items = {12, 24, 45, 56, 10, 9, 49, 30, 5, 15};
     printArray(items);

     System.out.println("\n\nAfter Mergesort");
     MergeSort merge = new MergeSort();
     merge.sort(items);
     printArray(items);

    }
}

Output

Original array before Merge sort
12 24 45 56 10 9 49 30 5 15 

After Mergesort
5 9 10 12 15 24 30 45 49 56