# Merge Sort Algorithm

Published Jan 18, 2024Updated May 15, 2024
Contribute to Docs

Merge sort is a divide-and-conquer sorting algorithm that breaks down an array into smaller arrays, sorts them, and then combines the subarrays back together to return a sorted array.

## MergeSort Method

Divide:

• `Base Case`: If the input array `data` has only one element, it’s already sorted, so return.
• `Split`: Divide the array into two halves, `left` and `right`, of approximately equal size.

Conquer:

• `Recursive Calls`: Repeatedly call `mergeSort` on each half, `(left)` and `(right)`, to create subarrays so they are sorted independently.

Combine:

• `Merge`: Call the `merge` function to merge the two sorted halves (each initially of length 1) `left` and `right`, and combine them back into the original array `data` in a sorted manner.

### Implementation Pt.1

The following example written in Java shows an implementation of the first part of the Merge Sort Algorithm — splitting the main array into subarrays:

```public static void mergeSort(int[] data){    if(data.length == 1){        return;    }    int n1 = data.length/2;    int n2 = data.length - n1;    int[] left, right;    //make left and right subarrays    left = new int[n1];    right = new int[n2];    System.arraycopy(data, 0, left, 0, n1);    System.arraycopy(data, n1, right, 0, n2);    //recursively split left and right arrays    mergeSort(left);    mergeSort(right);    //once array is @ length 1, the left & right array will be merged    merge(data, left, right);}
```

### Merge Method

1. Initialize:
• Set indices `l`, `r`, and `k` to 0 to track the positions in `left`, `right`, and `data`.
2. Compare and Merge:
• While both `left` and `right` have elements remaining:
• Compare the elements at `left[l]` and `right[r]`.
• Copy the smaller element into `data[k]` and increment the corresponding index (`l` or `r`).
• Increment `k` to move to the next position in `data`.
3. Copy Remaining Elements:
• If any elements remain in `left`, copy them directly into the remaining positions in `data`.
• Similarly, if any elements remain in `right`, copy them into the remaining positions in `data`.

### Implementation Pt.2

The following example written in Java shows an implementation of the second part of Merge Sort — sorting the subarrays and merging them back into the original array:

```public static void merge(int[] data, int[] left, int[] right){    //indexes of arrays left, right, and data    int l,r,k;    l = r = k = 0;    while(l < left.length && r < right.length && k < data.length){        //find min between left & right element and insert it        if(left[l] < right[r]){            data[k] = left[l];            l++;        }        else{            data[k] = right[r];            r++;        }        //increment index of data after insertion        k++;    }    //if elements still remain in arrays left or right, insert them into the data    while(l < left.length){        data[k] = left[l];        l++;        k++;    }    while(r < right.length){        data[k] = right[r];        r++;        k++;    }}
```

### Time Complexity Breakdown

Overall Time Complexity: O(n log n)

### Breakdown

1. Divide:

• The `mergeSort` function recursively divides the array into halves until each subarray has only one element.
• This splitting process has a time complexity of O(log n) due to the repeated halving.
2. Conquer:

• The base case (array of size 1) requires no sorting, so its complexity is O(1).
3. Combine:

• The `merge` function merges two sorted subarrays into a single sorted array.
• It iterates through both subarrays once, comparing elements and copying them to the final array.
• This merging process takes O(n) time, where n is the total number of merged elements.

Overall Time Complexity:

• The recursive calls to `mergeSort` create a log n-level tree.
• The number of levels in this tree directly relates to how many times the array can be divided by 2 before reaching single-element subarrays. This is equivalent to the logarithm of the array’s size (log n). For example, an array of 8 elements would have 3 levels (log2 (8) = 3). Reference the picture below for a visual understanding.

• At each level, the merging step takes O(n) time.
• Therefore, the overall time complexity is O(n log n), resulting from multiplying the time complexity of each level (n) by the number of levels (log n).

## Benefits of Merge Sort

• `Predictable Efficiency`: Merge sort maintains a time complexity of O(n log n) regardless of the initial arrangement of elements in the input array. This means it performs equally well in best-case, average-case, and worst-case scenarios.
• `Reliable for Diverse Inputs`: This consistent performance makes merge sort a dependable choice for sorting various input sizes and datasets without unexpected slowdowns due to data arrangement.
• `Efficiency for Large Datasets`: Its O(n log n) time complexity places it among the most efficient sorting algorithms, especially for large datasets, outperforming algorithms like bubble sort and selection sort that exhibit worse-case complexities of O(n^2).