# Typesetting Sorting Diagrams

I am typesetting some diagrams representing sorting algorithms similar to those found in Miller and Ranum Python Book partly as an exercise in learning TikZ. I'm trying to typeset something similar to the Merge sort diagrams:

Splitting phase:

Merging phase

I started with a multipart rectangle but the drop shadow overwrites the filled nodes (unless white) — on the second row I experimented with individual nodes but this leads to problems with fonts (such as Lucida) where not all digits have the dame height.

Here's my code for these parts:

\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{positioning}

\newlength{\OUmatrixSepWidth}
\newcommand{\OUsetMatrixSepWidth}[1]{%
\settowidth{\OUmatrixSepWidth}{#1}%
}

\renewcommand{\familydefault}{\sfdefault}
\thispagestyle{empty}

\begin{document}
\Large

\OUsetMatrixSepWidth{3em}

\begin{tikzpicture}
[myInnerBlock/.style={rectangle,draw,align=center}
,myInnerBlockL/.style={rectangle,draw,align=center,fill=red!20}
,myInnerBlockR/.style={rectangle,draw,align=center,fill=blue!20}
,myRectangleSplit/.style={rectangle split,rectangle split horizontal,draw,rectangle split part align={center,base}} % requires library shapes.multipart
,line/.style={draw,thick,red,-triangle 60}
]
\matrix[column sep=0.3\OUmatrixSepWidth, row sep=0.5\OUmatrixSepWidth]
{
% row 1
\node[myRectangleSplit,rectangle split allocate boxes=10,rectangle split parts=10,drop shadow,rectangle split part fill={red!20,red!20,red!20,red!20,red!20,blue!20}] (unsorted)
{ 3\nodepart{two}0\nodepart{three}1\nodepart{four}8\nodepart{five}7\nodepart{six}2\nodepart{seven}5\nodepart{eight}4\nodepart{nine}9\nodepart{ten}6}; \\
% row 2
\node (r2ac) {};
\node[myInnerBlockR,left=0.3\OUmatrixSepWidth of r2ac] (r2a5) {7};
\node[myInnerBlockR,left=0pt of r2a5] (r2a4) {8};
\node[myInnerBlockR,left=0pt of r2a4] (r2a3) {1};
\node[myInnerBlockL,left=0pt of r2a3] (r2a2) {0};
\node[myInnerBlockL,left=0pt of r2a2] (r2a1) {3};
\node[myInnerBlockL,right=0.3\OUmatrixSepWidth of r2ac] (r2a6) {2};
\node[myInnerBlockL,right=0pt of r2a6] (r2a7) {5};
\node[myInnerBlockR,right=0pt of r2a7] (r2a8) {4};
\node[myInnerBlockR,right=0pt of r2a8] (r2a9) {9};
\node[myInnerBlockR,right=0pt of r2a9] (r2a10) {6};
\\
% row 3
% row 4
% row 5
};
\end{tikzpicture}

\end{document}


Which looks like:

The multipart rectangle would appear nicer but how do you get the drop shadow to not overwrite the rectangle? Is there a better way that I'm missing ? Would a tree structure be easier ? Not to mention getting the lines with right angles.

-
You can use layers for that and put it in the background layer. – cacamailg Jun 10 '13 at 16:11
– cacamailg Jun 10 '13 at 16:26

Using your code and the answer from here: Drawing a proper shadow for overlapping objects, and adjusting the shadow yshift key, you can have shadows properly drawn. For extra info about shadows see page 415 on PGF manual.

\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{positioning}

\newlength{\OUmatrixSepWidth}
\newcommand{\OUsetMatrixSepWidth}[1]{%
\settowidth{\OUmatrixSepWidth}{#1}%
}

\renewcommand{\familydefault}{\sfdefault}
\thispagestyle{empty}

\pgfdeclarelayer{back}
\pgfsetlayers{back,main}
\makeatletter
\pgfkeys{%
/tikz/on layer/.code={
\pgfonlayer{#1}\begingroup
\aftergroup\endpgfonlayer
\aftergroup\endgroup
},
/tikz/node on layer/.code={
\pgfonlayer{#1}\begingroup
\expandafter\def\expandafter\tikz@node@finish\expandafter{\expandafter\endgroup\expandafter\endpgfonlayer\tikz@node@finish}%
},
}
\makeatother

\begin{document}
\Large

\OUsetMatrixSepWidth{3em}

\begin{tikzpicture}
[myInnerBlock/.style={rectangle,draw,align=center}
,myInnerBlockL/.style={rectangle,draw,align=center,fill=red!20}
,myInnerBlockR/.style={rectangle,draw,align=center,fill=blue!20}
,myRectangleSplit/.style={rectangle split,rectangle split horizontal,draw,rectangle split part align={center,base}} % requires library shapes.multipart
,line/.style={draw,thick,red,-triangle 60}
]
\matrix[column sep=0.3\OUmatrixSepWidth, row sep=0.5\OUmatrixSepWidth]
{
% row 1
=3ex},rectangle split part fill={red!20,red!20,red!20,red!20,red!20,blue!20}] (unsorted)
{ 3\nodepart{two}0\nodepart{three}1\nodepart{four}8\nodepart{five}7\nodepart{six}2\nodepart{seven}5\nodepart{eight}4\nodepart{nine}9\nodepart{ten}6}; \\[2ex]
% row 2
\node (r2ac) {};
\node[myInnerBlockR,left=0.3\OUmatrixSepWidth of r2ac] (r2a5) {7};
\node[myInnerBlockR,left=0pt of r2a5] (r2a4) {8};
\node[myInnerBlockR,left=0pt of r2a4] (r2a3) {1};
\node[myInnerBlockL,left=0pt of r2a3] (r2a2) {0};
\node[myInnerBlockL,left=0pt of r2a2] (r2a1) {3};
\node[myInnerBlockL,right=0.3\OUmatrixSepWidth of r2ac] (r2a6) {2};
\node[myInnerBlockL,right=0pt of r2a6] (r2a7) {5};
\node[myInnerBlockR,right=0pt of r2a7] (r2a8) {4};
\node[myInnerBlockR,right=0pt of r2a8] (r2a9) {9};
\node[myInnerBlockR,right=0pt of r2a9] (r2a10) {6};
\\
% row 3
% row 4
% row 5
};
\end{tikzpicture}

\end{document}


Result:

-
Thanks for this — very helpful. A couple of questions: (1) The row separation looks bigger in your case by quite some way (even though the row sep keys are the same; (2) The code for the pgfkeys is TeX — could it be written in LaTeX ? (3) The shadow yshift=3ex appears by magic — what is the base of the shift ? – Phil Molyneux Jun 11 '13 at 11:07
@PhilMolyneux In order to answer your questions: (1) and (3) If you look at the code you can see \\[2ex] in the of the splitted node; this means insert a new line with vertical space of 2ex. Next, I did some trials and verified that the shadow yshift need some adjustment, and one that looked better for me is 3ex; this means move shadow up by 3ex. As such, in the end the shadow only moved up 1ex (3ex-2ex). Four LaTeX units you can see here: tex.stackexchange.com/questions/8260/…. – cacamailg Jun 11 '13 at 12:20
@PhilMolyneux For question (2) PGF/TikZ is attached to TeX and, as such, can be used both in plain TeX, LaTeX or ConTeXt. Also LaTeX add some macros to TeX to make it more consistent and robust. But on this case I don't see a reason to change. – cacamailg Jun 11 '13 at 12:24