Animated Merge sort example

Question

I would like to create a merge sort example like this one on Wikipedia:Merge Sort. Can someone help me?

---

here is what I've done so far, but it doesn't work properly and effects are not like in this wikipedia example. Any improvement ? Thanks

\documentclass{beamer}
\usepackage{pgfpages}
\usepackage[ngerman]{babel}
\usepackage{animate}
\usepackage{tikz}
\usetikzlibrary{arrows,decorations.pathmorphing,through,backgrounds,positioning,fit,petri}
\usetikzlibrary{shapes,shadows}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{calc}
\usetikzlibrary{decorations.pathreplacing}
\newcounter{angle}
\setcounter{angle}{0}
\begin{document}

\begin{frame}
\begin{animateinline}[
  begin={%
\begin{tikzpicture}
\node[shape=rectangle, draw=black, minimum size=0.5cm](1) at (1,1) {6};
\node[shape=rectangle, draw=black, minimum size=0.5cm](2) at (1.5,1) {5};
\node[shape=rectangle, draw=black, minimum size=0.5cm](3) at (2,1) {3};
\node[shape=rectangle, draw=black, minimum size=0.5cm](4) at (2.5,1) {1};
\node[shape=rectangle, draw=black, minimum size=0.5cm](5) at (3,1) {8};
\node[shape=rectangle, draw=black, minimum size=0.5cm](6) at (3.5,1) {7};
\node[shape=rectangle, draw=black, minimum size=0.5cm](7) at (4,1) {2};
\node[shape=rectangle, draw=black, minimum size=0.5cm](8) at (4.5,1) {4};
\node(9) at (5.0,1) {};
\useasboundingbox (-0.5,-0.5) rectangle (10,9.5);},
  end={\end{tikzpicture}}
]{10}

\newframe*
\multiframe{2}{iCount=1+1}{
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (1) at (1,\iCount) {6};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (2) at (1.5,\iCount) {5};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (3) at (2,\iCount) {3};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (4) at (2.5,\iCount) {1};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (5) at (3.2,\iCount) {8};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (6) at (3.7,\iCount) {7};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (7) at (4.2,\iCount) {2};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (8) at (4.7,\iCount) {4}; 
}

\newframe*
\multiframe{2}{iCount=2+1}{
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (1) at (1,\iCount) {6};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (2) at (1.5,\iCount) {5};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (3) at (2.1,\iCount) {3};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (4) at (2.6,\iCount) {1};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (5) at (3.2,\iCount) {8};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (6) at (3.7,\iCount) {7};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (7) at (4.3,\iCount) {2};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (8) at (4.8,\iCount) {4}; 
}

\newframe*
\multiframe{2}{iCount=3+1}{
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (1) at (1,\iCount) {5};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (2) at (1.5,\iCount) {6};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (3) at (2.1,\iCount) {1};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (4) at (2.6,\iCount) {3};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (5) at (3.2,\iCount) {7};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (6) at (3.7,\iCount) {8};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (7) at (4.3,\iCount) {2};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (8) at (4.8,\iCount) {4}; 
}

\newframe*
\multiframe{2}{iCount=4+1}{
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (1) at (1,\iCount) {1};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (2) at (1.5,\iCount) {3};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (3) at (2.0,\iCount) {5};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (4) at (2.5,\iCount) {6};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (5) at (3.2,\iCount) {2};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (6) at (3.7,\iCount) {4};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (7) at (4.2,\iCount) {7};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (8) at (4.7,\iCount) {8}; 
}

\newframe*
\multiframe{2}{iCount=5+1}{
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (1) at (1,\iCount) {1};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (2) at (1.5,\iCount) {2};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (3) at (2.0,\iCount) {3};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (4) at (2.5,\iCount) {4};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (5) at (3.0,\iCount) {5};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (6) at (3.5,\iCount) {6};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (7) at (4.0,\iCount) {7};
    \node[shape=rectangle, draw=black, minimum size=0.5cm] (8) at (4.5,\iCount) {8}; 
}
\end{animateinline}
\end{frame}

\end{document} 

Answer 1

Here's an idea using blue circles to indicate what's done next. It's just a concept, hardcoding the actual thing will be a real pain (therefore I won't do it). Feel free to edit or delete this.

Code

\documentclass{beamer}
\usepackage{tikz}
\usetikzlibrary{arrows}

% scaling factor of the picture
\pgfmathsetmacro{\scalefactor}{0.40}

% styles for boxes, arrows, and the circles 
\tikzset%
{   mybox/.style={thick, minimum width=2cm*\scalefactor, minimum height=2cm*\scalefactor, text=black, inner sep=0},
    myarrow/.style={thick,-latex,blue},
    myhighbox/.style={circle,draw=blue,thick, minimum width=3.3cm*\scalefactor}
}

\begin{document}

\begin{frame}

\begin{tikzpicture}[scale=\scalefactor]

% help grid
    \draw[gray] (0,0) grid (23,11);
%   help labels
    \foreach \x in {0,2,...,22} \draw (\x,0) -- (\x,-0.5) node[below] at (\x,0) {\x};
    \foreach \x in {0,2,...,10} \draw (0,\x) -- (-0.5,\x) node[left] at (0,\x) {\x};

% cycle over all states of boxone; state=[x-pos, y-pos, color, statestart(frame), stateend(frame)]
    \foreach \x/\y/\col/\startframe/\endframe in {1/3/red/1/3, 12/4/black/4/5, 19/1/red/6/6}
    {   \node<\startframe-\endframe>[mybox,draw=\col] at (\x,\y) {1};
    }

% cycle over all states of boxtwo; state=[x-pos, y-pos, color, statestart(frame), stateend(frame)]  
    \foreach \x/\y/\col/\startframe/\endframe in {10/7/black/1/2, 20/1/black/3/4, 4/2/red/5/6}
    {   \node<\startframe-\endframe>[mybox,draw=\col] at (\x,\y) {2};
    }

% ... and so on for all boxes

% cycle over all states of arrows; state=[x1, y1, x2, y2, frame]
    \foreach \xa/\ya/\xb/\yb/\fra in {1/3/12/4/3, 12/4/19/1/5, 10/7/20/1/2, 20/1/4/2/4}
    {   \node<\fra>[myhighbox] (startbox) at (\xa,\ya) {};
        \node<\fra>[myhighbox] (endbox) at (\xb,\yb) {};
        \draw<\fra>[myarrow] (startbox) -- (endbox);
    }

% just a help to show how the boxes could be positioned in certain steps    
    \foreach \x [count=\c] in {1,4,...,22} \node<7>[mybox,fill=green!20,draw=black] at (\x,1) {\c};
    \foreach \x [count=\c] in {3,5,8,10,13,15,18,20} \node<7>[mybox,fill=green!20,draw=black] at (\x,4) {\c};
    \foreach \x [count=\c] in {4,6,8,10,13,15,17,19} \node<7>[mybox,fill=green!20,draw=black] at (\x,7) {\c};
    \foreach \x [count=\c] in {4.5,6.5,...,18.5} \node<7>[mybox,fill=green!20,draw=black] at (\x,10) {\c};

\end{tikzpicture}

\end{frame}

\end{document}

Result