## CODEX

# Merge Sort Algorithm

## Divide and Conquer Recursion

## Explanation

In 1945 John von Neumann, the Hungarian mathematician, physicist, and computer scientist, developed the merge sort algorithm. Merge sort is a general-purpose sorting method that uses a ‘divide and conquer’ approach. It was developed to address weaknesses in less efficient algorithms such as bubble sort. It is the classic example of a recursive bottom-up ‘divide and conquer’ algorithm in many ways. Despite this, a top-down looping approach is possible. For this article, I will explain merge sort with the former perspective.

## PsuedoCode

PROCEDURE MERGESORT(ARRAY)

IF(ARRAY.LENGTH == 1) THEN

RETURN ARRAY

ELSE IF(ARRAY.LENGTH ==2) THEN

RETURN [MIN(ARRAY),MAX(ARRAY)]

ELSE

RETURN COMBINE(

MERGESORT([ARRAY[0]...ARRAY[length/2]]),

MERGESORT([...ARRAY[length/2 + 1]]))

END IFPROCEDURE COMBINE(ARRAYA,ARRAYB)

LOOP THROUGH LARGERARRAY

IF ARRAYA[i] < ARRAYB[i] THEN

PUSH ARRAYA[i] > EMPTYARRAY

ELSE

PUSH ARRAYB[i] > EMPTYARRAY

ENDIF

RETURN COMBINEARRAY

END PROCEDURE

END PROCEDURE

Looking at the pseudocode above, we can see that the algorithm consists of two important sections. First, an ‘if-else’ conditional branch is combined with a recursive call. Second, this recursive call is helped with a ‘helper’ procedure that combines two previous sorted arrays.

The basic logic flows as follows:

- If the array length is one, return the array.
- If the array length is two, return the sorted array by simply swapping the min value and maximum value.
- If the array length is larger than two, split the array in half.
- Then recursively call merge sort on each of those halves.
- On the return of these recursive calls, combine the two already sorted half arrays.
- As the recursive calls return from the stack, the eventual product is a fully sorted array.

## Implementation

The merge sort algorithm is implemented in JavaScript below.

//main mergeSort function-implements top down recursive approach

function mergeSort (unsortedArray) {

//return array back if length is 1

if (unsortedArray.length <= 1) {

return unsortedArray;

//return [min,max] if array has only two elements

} else if(unsortedArray.length <= 2) {

return [Math.min.apply(null,unsortedArray),

Math.max.apply(null,unsortedArray)]

}

//if array has more than two elements it must be split

//first find middle point

const middle = Math.floor(unsortedArray.length / 2);

const left = unsortedArray.slice(0, middle);

const right = unsortedArray.slice(middle);

// With the array now split in two recursively call merge Sort and

//combine results

return merge(mergeSort(left),mergeSort(right));

}

//Merge combines reults of two merge sorts

function merge (left, right) {

let resultArray = [], leftIndex = 0, rightIndex = 0;

while (leftIndex < left.length && rightIndex < right.length) {

if (left[leftIndex] < right[rightIndex]) {

resultArray.push(left[leftIndex]);

leftIndex++;

} else {

resultArray.push(right[rightIndex]);

rightIndex++;

}

}return [...resultArray, ...left.slice(leftIndex),...right.slice(rightIndex)]

}

The JavaScript implementation uses a mergeSort function that handles most of the logic coordination and a “helper” function that combines already sorted arrays. The flow of the program is illustrated below with an example array: [7,3,5,8,13,1,2,99,9,4].

## Time and Space Complexity

Merge Sort’s time complexity is determined by the number of comparisons that occur through the algorithm. Like most “divide and conquer” algorithms, one of its terms is logarithmic. Looking at the tree diagram above, we can see that the worst-case n comparisons are made at every tree level. Each level represents a finer division of the number list. Therefore the time complexity will be n times the height of the binary tree above. Consequently, the final time complexity is:

*f*(*n*)=O(*n*(*ln*(*n*))), where n is the size of input array

The algorithm does require the creation of two sub-arrays in addition to the original array. This is necessary for the recursive calls to work properly. Consequently, the algorithm must create n elements in memory. Thus the space complexity is O(n).

## Key TakeAways

- Merge sort algorithm sorts a list or array using a divide and conquer strategy. John von Neumann developed it in 1945.
- It uses a divide and conquer method. This method can be implemented bottom-to-up recursively or top-to-bottom with a loop.
- The Merge Sort algorithm has a space and time complexity of O(n) and O(n ln n).