# Example: Merge sort recursion tree

Published 2009-12-16 | Author: Manuel Kirsch

Do you have a question regarding this example, TikZ or LaTeX in general? Just ask in the LaTeX Forum.
Oder frag auf Deutsch auf TeXwelt.de. En français: TeXnique.fr.

% MergeSort-RecursionTree
% Manuel Kirsch
\documentclass[a4paper,landscape]{scrartcl}
\usepackage{fancybox}
\usepackage{tikz}

\title{MergeSort-RecursionTree}
\author{Manuel Kirsch}
\date{}
\begin{document}

\ovalbox{
\begin{tikzpicture}[level/.style={sibling distance=60mm/#1}]
\node [circle,draw] (z){$n$}
child {node [circle,draw] (a) {$\frac{n}{2}$}
child {node [circle,draw] (b) {$\frac{n}{2^2}$}
child {node {$\vdots$}
child {node [circle,draw] (d) {$\frac{n}{2^k}$}}
child {node [circle,draw] (e) {$\frac{n}{2^k}$}}
}
child {node {$\vdots$}}
}
child {node [circle,draw] (g) {$\frac{n}{2^2}$}
child {node {$\vdots$}}
child {node {$\vdots$}}
}
}
child {node [circle,draw] (j) {$\frac{n}{2}$}
child {node [circle,draw] (k) {$\frac{n}{2^2}$}
child {node {$\vdots$}}
child {node {$\vdots$}}
}
child {node [circle,draw] (l) {$\frac{n}{2^2}$}
child {node {$\vdots$}}
child {node (c){$\vdots$}
child {node [circle,draw] (o) {$\frac{n}{2^k}$}}
child {node [circle,draw] (p) {$\frac{n}{2^k}$}
child [grow=right] {node (q) {$=$} edge from parent[draw=none]
child [grow=right] {node (q) {$O_{k = \lg n}(n)$} edge from parent[draw=none]
child [grow=up] {node (r) {$\vdots$} edge from parent[draw=none]
child [grow=up] {node (s) {$O_2(n)$} edge from parent[draw=none]
child [grow=up] {node (t) {$O_1(n)$} edge from parent[draw=none]
child [grow=up] {node (u) {$O_0(n)$} edge from parent[draw=none]}
}
}
}
child [grow=down] {node (v) {$O(n \cdot \lg n)$}edge from parent[draw=none]}
}
}
}
}
}
};
\path (a) -- (j) node [midway] {+};
\path (b) -- (g) node [midway] {+};
\path (k) -- (l) node [midway] {+};
\path (k) -- (g) node [midway] {+};
\path (d) -- (e) node [midway] {+};
\path (o) -- (p) node [midway] {+};
\path (o) -- (e) node (x) [midway] {$\cdots$}
child [grow=down] {
node (y) {$O\left(\displaystyle\sum_{i = 0}^k 2^i \cdot \frac{n}{2^i}\right)$}
edge from parent[draw=none]
};
\path (q) -- (r) node [midway] {+};
\path (s) -- (r) node [midway] {+};
\path (s) -- (t) node [midway] {+};
\path (s) -- (l) node [midway] {=};
\path (t) -- (u) node [midway] {+};
\path (z) -- (u) node [midway] {=};
\path (j) -- (t) node [midway] {=};
\path (y) -- (x) node [midway] {$\Downarrow$};
\path (v) -- (y)
node (w) [midway] {$O\left(\displaystyle\sum_{i = 0}^k n\right) = O(k \cdot n)$};
\path (q) -- (v) node [midway] {=};
\path (e) -- (x) node [midway] {+};
\path (o) -- (x) node [midway] {+};
\path (y) -- (w) node [midway] {$=$};
\path (v) -- (w) node [midway] {$\Leftrightarrow$};
\path (r) -- (c) node [midway] {$\cdots$};
\end{tikzpicture}}

\end{document}


• #1 Brett Bellomo, March 8, 2010 at 8:28 p.m.

What about only natural recursion? Any quizzes on subject? 4 yrs common Java,Msoft Charted recursion(computers?

• #2 Tobias Mueller, August 24, 2010 at 10:24 a.m.

I can't compile that document :(

\$ pdflatex tikz.tex This is pdfTeXk, Version 3.141592-1.40.3 (Web2C 7.5.6) %&-line parsing enabled. entering extended mode (./tikz.tex LaTeX2e <2005/12/01> [...] (/usr/share/texmf/tex/generic/pgf/libraries/pgflibraryplothandlers.code.tex) (/usr/share/texmf/tex/generic/pgf/libraries/pgflibrarytikztopaths.code.tex))) (./tikz.aux) (/usr/share/texmf/tex/context/base/supp-pdf.tex [Loading MPS to PDF converter (version 2006.09.02).] ) ! Illegal parameter number in definition of \tikz@key@rest. 1 l.11 ...}[level/.style={sibling distance=60mm/#1}]

? X No pages of output. Transcript written on tikz.log.

• #3 Barun Saha, February 21, 2012 at 9:24 p.m.

That's superb! I didn't knew such beautiful things could be done with LaTeX!

• #4 sisay, November 23, 2012 at 7:28 a.m.

i ask one question gives the analysis algorithm notes and with examples?

• #5 Adam S-W, March 7, 2013 at 3:03 p.m.

Hi, I really like the look of this tree and the simple commands. I want to use it to make some tableaux for first order logic, which means I'll need to be able to put non-branching lines of text right under each other:

A B C

like so,

Is there an easy way to do this?

Thanks 