CODEX

Merge Sort Algorithm

Divide and Conquer Recursion

Photo by Steve Johnson on Unsplash

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 IF
PROCEDURE 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…