Merge Sort
A divide & conquer sorting algorithm with runtime-page 12, [complexity](com1009-l03-divide-and-conquer) \( \theta(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 += 1Warn: Merge sort has space-complexity \( \Omega(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}