Merge sort explanation in java

Merge sort Algorithm in java.

---

Given a unsorted array, Sort it using Merge Sort Algorithm.

Lets understand what is the input and the expected output.

Sort array using merge sort in java

Merge sort Algorithm

---

How Merge Sort works

1. Merge Sort works by breaking the array into 2 equal parts say Left half and Right half.
2. Again break 2 sub array that we got in Step 1 in two equal parts each.  
3. Repeat above steps until only 1 element remains in array because array with only one element is always sorted. 
4. So in each step we are breaking the array in Left half and Right half.  
5. When complete array is divided and contains only Single element in Left and Right half each, Start comparing and sort each Left and Right half, So that portion of array will be sorted.
6. Repeat Step 5 for all the remaining Left and Right sub-array and complete array will be sorted.

Merge sort Time complexity

---

Merge sort time complexity is O(N log N).

Lets understand with the help of below example.

Merge sort algorithm with example

Java program to sort an array using merge sort

---

package com.javabypatel;

public class MergeSort {

    public static void main(String[] args) {
        int arr[] = {10, 1, -2, 8, 9, 10, 1};

        //Before sort
        print(arr);

        mergeSort(arr, 0, arr.length - 1);

        //After sort
        print(arr);
    }

    static void mergeSort(int arr[], int start, int end) {
        if (start >= end)
            return;

        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    static void merge(int[] arr, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int counter = 0;

        int[] tempArr = new int[(end - start) + 1];

        while (i <= mid && j <= end) {
            if (arr[j] < arr[i]) {
                tempArr[counter] = arr[j];
                j++;
            } else {
                tempArr[counter] = arr[i];
                i++;
            }
            counter++;
        }
        while (i <= mid) {
            tempArr[counter] = arr[i];
            i++;
            counter++;
        }

        while (j <= end) {
            tempArr[counter] = arr[j];
            j++;
            counter++;
        }

        for (int k = 0; k < counter; k++) {
            arr[start + k] = tempArr[k];
        }
    }

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

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.