Smooth Sorting

Sorting algorithms (such as Bubble Sort and Quicksort) basically take a list of numbers as an input and output a permutation of that list in which list elements are in non-decreasing order. At a fundamental level, sorting the elements of a list involves accessing, storing and comparing elements. The various sorting algorithms are classified according to their computational complexity and memory usage. Sorting algorithms are “as discrete as it gets”, and every computer science student has learned them in some detail.

Having said that, I was indeed shocked (I’m not exagerating!) when I found at the Harvard Robotics Lab’s site a sorting algorithm based on coupled nonlinear ordinary differential equations (ODEs)! That is a dramatically new framework! The algorithm is named Smooth Sorting, and it seems to have been developed by Prof. Roger Brockett and his research group (I don’t know exactly because they don’t have much info on that on the HRL website).

In my own words, here’s a description of the Smooth Sorting algorithm…

Let’s say we want to sort a list of numbers. Instead of using the conventional sorting algorithms, we could use the following set of coupled nonlinear ODEs

.

From the HRL’s page, we know that the variables are initialized with the numbers to be sorted, and the variables are initialized with some small non-zero values (why?). The HRL people say that the variables will flow from their initially unsorted state to a sorted state. I believe in them… especially after watching this video (AVI – 872 KB):

[ courtesy of Harvard HRL ]

Here’s an excerpt from the HRL Analog Computing page:

Sorting numbers seems to be an intrinsically “discrete” task. By this we mean that all intuitive algorithms to perform sorting involve a set of indivisible steps such as swapping the position of two values. Surprisingly, sorting can also be achieved in a smooth way. The following set of differential equations allows a set of unsorted numbers to flow toward the sorted state in a continuous way. (…) This system is also known as the nonperiodic finite Toda lattice.

I am still trying to understand why the variables will converge to a desired sorted state. This is one of the coolest findings of the year! I am trying to find scientific papers related to this topic, and I will be writing more soon. If you have some ideas and critiques, feel most welcome to share them.

Tags: Analog Computing, Differential Equations, Recreational Mathematics, Smooth Sorting, Sorting Algorithms