Merge Sort

Tags: comp-sci algorithm

A divide & conquer sorting algorithm with runtime-page 12, [complexity](com1009-l03-divide-and-conquer) $θ (n \log n)$ .

It [see page 4, works] by:

Divide: the $n$ -element sequence to be sorted into 2 sub-sequences of $\frac{n}{2}$ elements.
Conquer: sort the two sub-sequences recursively using merge-sort.
Combine: merge the two sub-sequences back together to produce the sorted answer.

Formulation

def merge_sort(arr):
    if len(arr) <= 1:
	return

    mid = len(arr) // 2
    l, r = arr[:mid][:], arr[mid:][:]

    merge_sort(l)
    merge_sort(r)

    # Sort the elements in the range.
    i = j = k = 0
    while i < len(l) and j < len(r):
	if l[i] < r[j]:
	    arr[k] = l[i]
	    i += 1
	else:
	    arr[k] = r[j]
	    j += 1
	k += 1

    # Place any remaining elements.
    while i < len(l):
	arr[k] = l[i]
	i += 1
	k += 1
    while j < len(r):
	arr[k] = r[j]
	j += 1
	k += 1

Code Snippet 1: Merge sort implementation. alg:merge-sort

Warn: Merge sort has space-complexity $Ω (n)$ because you have to copy the left and right divided array so that you can merge them back into the original array without any reference mismatches. Merge-sort can be implemented in-place but it's not easy.

You can see the implementation of merge-sort in alg:merge-sort. At a high level merge-sort works by moving a pointer through the head of two sorted sub-arrays in sequence, placing the smaller element at the tip of the original array such that by the time you've traversed both sorted sub-arrays you've filled the original array with elements in sorted order. It avoids excess comparisons by only ever comparing the smallest elements of each sub-array.

\def\lvld{1.2}                  % Level distance
\pgfmathsetmacro\shft{-6*\lvld} % Calculate the yshift for the green tree

\begin{figure}
  \centering
  \begin{tikzpicture}[level distance=\lvld cm,
    level 1/.style={sibling distance=4cm},
    level 2/.style={sibling distance=2cm},
    level 3/.style={sibling distance=1cm},
    edgedown/.style={edge from parent/.style={draw=red,thick,-latex}},
    edgeup/.style={edge from parent/.style={draw=green!50!black,thick,latex-}},
    block/.style={
      font=\sffamily,
      draw=black,
      thin,
      fill=pink!50,
      rectangle split,
      rectangle split horizontal,
      rectangle split parts=#1,
      outer sep=0pt},
    gblock/.style={
      block,
      rectangle split parts=#1,
      fill=green!30}
    ]

    % Splitting
    \node[gblock=7,yshift=\shft cm] (A') {3 \nodepart{two} 9 \nodepart{three} 10 \nodepart{four} 27 \nodepart{five} 39 \nodepart{six}43 \nodepart{seven}82}
    [grow=up,edgeup]
    child {node[gblock=3] (B2') {9 \nodepart{two} 10 \nodepart{three} 82}
      child {node[gblock=1] (C4') {10}
	child {node[gblock=1] (D7') {10}}
      }
      child {node[gblock=2] (C2') {9 \nodepart{two} 82}
	child {node[gblock=1] (D3') {82}}
	child {node[gblock=1] (D4') {9}}
      }
    }
    child {node[gblock=4] (B1') {3 \nodepart{two} 27 \nodepart{three} 39 \nodepart{four} 43}
      child {node[gblock=2] (C3') {3 \nodepart{two} 43}
	child {node[gblock=1] (D5') {3}}
	child {node[gblock=1] (D6') {43}}
      }
      child {node[gblock=2] (C1') {27 \nodepart{two} 39}
	child {node[gblock=1] (D1') {27}}
	child {node[gblock=1] (D2') {39}}
      }
    };

    % Merging
    \node[block=7] (A) {39 \nodepart{two} 27 \nodepart{three} 43 \nodepart{four} 3 \nodepart{five} 9 \nodepart{six}82 \nodepart{seven}10}
    [grow=down,edgedown]
    child {node[block=4] (B1) {39 \nodepart{two} 27 \nodepart{three} 43 \nodepart{four} 3}
      child {node[block=2] (C1) {39 \nodepart{two} 27}
	child {node[block=1] (D1) {39}}
	child {node[block=1] (D2) {27}}
      }
      child {node[block=2] (C2) {43 \nodepart{two} 3}
	child {node[block=1] (D3) {43}}
	child {node[block=1] (D4) {3}}
      }
    }
    child {node[block=3] (B2) {9 \nodepart{two} 82 \nodepart{three} 10}
      child {node[block=2] (C3) {9 \nodepart{two} 82}
	child {node[block=1] (D5) {9}}
	child {node[block=1] (D6) {82}}
      }
      child {node[block=1] (C4) {10}
	child {node[block=1] (D7) {10}}
      }
    };
  \end{tikzpicture}
  \caption{An example of merge-sort in action.}
\end{figure}