The Merge Sort algorithm is one of the most basic "Divide-and-Conquer" algorithms. The input array is first divided in half, so for this 10-element array, each half has 5 elements. Then the 5-element sections are divided into a 3-element and 2-element section. The 3-element sections are divided into a 2-element and a 1-element section. Then even the 2-element sections are divided into 2 1-element sections.

Next comes the "Merging", where all these smaller divisions are progressively merged together, so that the smaller elements are placed in front of the larger elements. Essentially, two sections to be merged are "zippered" together, to form a combined sorted section. In this animation, you will see that first, elements #1 and #2 are merged, then this is merged with element #3. Next, elements #4 and #5 are merged, so that now we have 2 sorted sections: elements #1 through #3 sorted, and elements #4 through #5 sorted. Then, these two sections (#1 - #3) and (#4 - #5) are merged.

This exact process is repeated for the second half (elements #6 - #10) of the array. So before the final merge, we have 2 sections (#1 - #5), and (#6 - #10), which are each independently sorted. Finally, these two sections are merged, which results in a fully sorted array. Please click the "Restart" button, to see for yourself that the final step is the merging of these two sorted sections. The entire animation for sorting 10 elements takes less than 30 seconds.

Programming your own cool graphics is pretty fun, and with the Three.js JavaScript library, you can do it in 3D. Three.js offers an overwhelming number of configuration parameters, especially with regard to the options for the viewing "camera". Consequently, the learning curve for doing even something simple with Three.js is pretty steep.

Choosing reasonable values for the options to the Camera can be a hit-and-miss process. Then if you want to change the Camera options after you have created the drawing, you must call several methods such as camera.position.set, camera.lookAt, and camera.updateProjectionMatrix.

Setting up the "Scene" object also has an huge number of options, including choosing the "Lighting" of the Scene. You can add any number of "DirectionalLight", "AmbientLight", "PointLight", and "SpotLight" objects to the Scene. So first I wrote some JavaScript "wrapper" classes around the THREE.Camera and THREE.Scene objects, which automatically choose some reasonable default values based on the dimensions you set.

I also created some wrapper objects over the standard THREE.Object3D objects, such as a custom "Bar" class, which adds functions to allow you to color each side of a rectangular cube individually. The built-in THREE.CubeGeometry object does not allow access to its internal THREE.Face objects, nor does it create line objects representing the edges of the cube. In addition, even drawing the underlying grid is not a built-in feature, so a I added a utility function for creating the grid.

Then I decided to write a jQuery-UI control panel to allow the user to adjust some of the camera parameters on-the-fly. The most useful controls are for the Camera Angle and Camera Height. The Camera Angle control is adjusted by using your mouse and dragging (click and holding down while moving the mouse) along the red dot around the circle slider widget. The "Ortho" controls set the edges of the viewport.

Wow, that was a lot of work. But now that is done, it's really easy to write new programs to display your 3D objects, and manipulate the viewing parameters interactively.

Three.js has a basic built-in Animation class, but it is designed for a single Animation action. To display the actions performed by Merge Sort, I needed to execute a series of synchronous (in-order) animation tasks for each Merge operation.

JavaScript is, by design, an asynchronous programming language. All functions are submitted to the JavaScript execution queue, and they may or may not be executed at the exact time desired. A call to an animation function, is actually a call to a function that calls itself repeatedly (typically using the built-in setTimeout function) to update an objects properties, such as position, angle or color. The animation function compares the actual elapsed time to the specified animation duration, and exits the loop when the final animation time is reached.

To execute a series of tasks in sequential order in JavaScript, the easiest way is to use an off-the-shelf "Promise" library, such as Q.js, Promise.js, RSVP.js, or When.js. There is ".promise" function in jQuery, but this ties the "Promise" to a DOM (the browser's Document Object Model) element, and so is prone to "Memory Leaks" (unreleased allocated memory) if you don't explicitly delete these objects upon failures (exceptions) in the task functions.

Each of these off-the-shelf solutions, implements the generic Promise API with "deferred" objects and functions on these objects typically called "when". These libraries differ in their memory footprint and optional features. For the synchonous animations tasks required here, I chose to use "When.js", which is offers a good balance of features vs. complexity.

This was not the first time I needed to create my own library of custom animation features. I've learned a lot by previous programming experience with the updated graphics framework for Java, called JavaFX. I have written a similar program to this Merge Sort Animation in JavaFX, which had a lot of additional features, such as highlighting the repeated divisions in the array. The unfortunate part of programming in JavaFX, is that the final product is Java applet. When a user tries to run a Java Applet in your web page, the browser displays 2 ominous "Security Warnings", and most people wisely chose not to risk running a non-essential program (no matter how safe you tell them it is).

Now that there are fast JavaScript Engines, such as the Google Chrome V-8 or the Mozilla (FireFox) SpiderMonkey engine, users can run graphical-intensive programs right in their browser at reasonable speeds (up to 80% the speed of a native program written in C or C++). The latest versions of most browsers now have support for the advanced WebGL API, which uses hardware acceleration built into modern CPUs to render graphics.

Even most new smart phones can run graphically intensive WebGL programs, and finally Apple has announced that its mobile browsers running iOS 8 will support WebGL after the update to be released in Fall 2014. But this Merge Sort Animation is not so graphically intensive that it requires WebGL support. So if your browser does not have WebGL enabled, this JavaScript program detects that and will fall back to rendering with the standard HTML5 Canvas API. For a graphically intensive program, not having hardware acceleration could result in the animation appearing jerky. However, this animation runs fine even without WebGL.

Borrowing on the flexible design pattern of JavaFX's "ObservableList" object, I designed 3 custom classes in JavaScript, which offer a fine level control suitable for any animation:

1. AnimationQueue: a wrapper to the Promise library, which allows addition of new animation tasks, and automatically executes any tasks remaining in the queue after they have reached completion. As the latest task in the queue is removed, it calls AnimationTask.update repeatedly, until its specified animationElapsedTime is reached.

2. AnimationTask: an object which defines the total elapsed time a task should be executed, and two internal arrays. One array is for the objects to be animated, and the second array is for the methods to be executed at each time step in the animation. Most importantly, the AnimationTask object calls the ".when" method of the Promise library at completion, which automatically signals the AnimationQueue method to "pop" (take off) the next task in the queue.

3. AnimationMethod: a class of methods, such as InterpolateMove, InterpolateRotate, InterpolateColor, TickMove, TickRotate, and TickColor, which allow specification of the precise change in each object for every time increment in the animation. To create a new AnimationMethod object, all you have to do is specify the properties of the object (such as position) at both the beginning and the end of the AnimationTask. The object itself automatically computes the properties at in-between times as the animation progresses. The AnimationTask object has an ".add" method, which requires a pair of AnimationMethod and THREE.Object3D objects to be simultanously added to AnimationTask's internal arrays.

The real flexibility designed in this system is that the AnimationTask object allows any number of objects to have individual properties changed at each time step in an animation. For example, in a single step in the "Merge" function, there are 3 separate AnimationTask objects.

1. The first Task moves the "Bar" ( the 3D rectangular object representing the value/height of the array element) forward.

2. The second Task slides this Bar to the left.

3. The really cool part is the third Task, which is the sum of multiple "AnimationMethod" objects. One is to return the moved Bar backward into the orginal line. Then, for each Bar that needs to be shifted to the right, an AnimationTask is added which specifies the beginning and end positions of the movement of each Bar to the right.

I wrote a JavaScript function called reorderBars, that perform these three tasks above. All that has to be specified is the index of the Bar to be moved, and the index of its destination. This function creates the 3 AnimationTask objects just described, and the all required AnimationMethod objects, and then just adds them to the AnimationQueue object.

So from the top, the whole program consists of these processes:

1. Create the base THREE.js Scene and Camera objects and add the grid.

2. Assign random values (heights) to each of the Bars and add them to the Scene object. Call Scene.render() to draw the initial static graph onto the web page.

3. Create the AnimationQueue object.

4. Start the MergeSort method. The merge method calls the reorderBars function when needed, which adds all the tasks to the AnimationQueue.

5. Call AnimationQueue.start(), which automatically executes each AnimationTask in order.

Please press Restart, then sit back and enjoy the ride!