Merge Sort... Sort Of

I have a project in mind that requires a sorting algorithm.  That's easy enough, there are plenty of them out there, the problem I have is that I want to be able to save the state of the sort part way through and resume it later.  The easiest way to explain the solution I devised is to show an example sort in the animation below and then explain it.  First understanding Merge Sort will help as well.

Custom Merge Sort

I haven't really changed much.  I've just implemented Merge Sort in a simple way.  More specifically in a list of lists.  The basic principles of a Merge Sort are still there.  At every stage all sub lists remain sorted and merging two lists is done by comparing the smallest elements of the two lists.

In the animation above, 11 numbers are sorted.  To start, 11 lists that contain only one number each are created to store the numbers to sort.  These are contained within another list that has another empty list placed at the start.  This empty list is called the auxiliary list or List 1.  From this point on the process is simple, merge List 2 and 3 into List 1.  Once this has been done, move the new large list to the end of the outer list. Each time this process is repeated, the number of lists is reduced by one until only one sorted list remains.  It also ensures the the lists are always ordered by the number of elements they contain.  Large ones at the end, smaller ones near the start.

The reason I like this method of sorting is that it's easy to pause the sort, save the state, and resume it later.  All you need to do is save a lists of lists.  You don't need anything else.  When resuming, the next move to make can be determined by looking at the first three lists and seeing if they contain any elements.

Sorting State

It's not ground breaking, and merge sort has probably been implemented like this before, but I found it to be a simple way to go about doing things.  I've mentioned lists throughout this post, but as the program I want to write is likely to be in python, I'll probably use a deque of deques to hold the data.

On another topic, my original plan way to make a nice fancy animation to explain things that had nice transitions, but I just couldn't pull it together in time.  I thought I could find a software package to do it and ended up with Synfig, but that went nowhere.  What kind of program freezes because you have a font installed it can't read.  Some error handling would be nice.

I eventually started hand coding an animated SVG and that showed promise, but it was a bit clumsy and I didn't really have a work flow established as you can see in the image below.  I think I've finally come to a solution that involves d3.js and all that's associated with it.  Fingers crossed.

Makeshift animated SVG IDE

Just for fun, let's speed things up. :-)

Fast Custom Merge Sort

.