# Merge Sort Algorithm

THE-Spellchecker154 total contributions

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 subarraysleft = 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 arraysmergeSort(left);mergeSort(right);//once array is @ length 1, the left & right array will be mergedmerge(data, left, right);}

### Merge Method

**Initialize**:- Set indices
`l`

,`r`

, and`k`

to 0 to track the positions in`left`

,`right`

, and`data`

.

- Set indices
**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`

.

- Compare the elements at

- While both
**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`

.

- If any elements remain in

### 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 dataint 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 itif(left[l] < right[r]){data[k] = left[l];l++;}else{data[k] = right[r];r++;}//increment index of data after insertionk++;}//if elements still remain in arrays left or right, insert them into the datawhile(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

**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.

- The
**Conquer**:- The base case (array of size 1) requires no sorting, so its complexity is
*O(1).*

- The base case (array of size 1) requires no sorting, so its complexity is
**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.

- The

**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.*

- 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).

- 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).

## All contributors

- THE-Spellchecker154 total contributions
- justin.code.ny3 total contributions

### Looking to contribute?

- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.