## What do the sounds mean?

This javascript program runs each sorting algoritm on the given array of pitches (as MIDI values). Each time a pitch is read from the array, the pitch is played softly, and each time a pitch is written to the array, the pitch is played loudly. Swaps and comparisons are played as intervals (with both pitches sounding simultaneously.)

## Why did you make this?

I built this for an electronic composition called Sorted Affairs. The entire composition process took many hours spread over several months.

## How does it work?

This program was written in Javascript using the jQuery, Raphaël, and MIDI.js libraries for animation and sound. In order to accomodate the timing necessary for animation and sound, each algoritm had to be altered extensively using 'setTimout' to allow for delays between reads and writes to the array.

Here is an example with one of the simplest algorithms, Bubble sort. This is the original Bubble sort algorithm:

```js
function bubbleSort(array) {
  var swapped;
  do {
    swapped = false;
    for (var i = 0; i < array.length - 1; i++) {
      if (compare(array, i, i + 1) > 0) {
        swap(array, i, i + 1);
        swapped = true;
      }
    }
  } while (swapped);
}
```

...and this is the function rewritten to allow delays for animation and sound:

```js
function bubbleSortAsync(array, callback) {
  (function bubbleSortWhileLoop() {
    swapped = false;
    (function bubbleSortForLoop(i) {
      setTimeout(function() {
        var test = compare(array, i, i + 1) > 0;
        setTimeout(
          function() {
            if (test) {
              swap(array, i, i + 1);
              swapped = true;
            }
            if (++i < array.length - 1) bubbleSortForLoop(i);
            else {
              if (swapped) bubbleSortWhileLoop();
              else if (callback) callback();
            }
          },
          test ? delay : 0
        );
      }, delay);
    })(0);
  })();
}
```

This isn't too bad with something like Bubble sort, as there are only two loops and no complex recursion. However, this process can become pretty tedious with a more complicated algorithm. Take Merge sort for example, which I found easiest to implement with a sort of make-shift call stack. This is what the time-delayed Merge sort algoritm ended up looking like:

```js
function mergeSortAsync(array, callback) {
  var stack = [];

  function executeFromStack() {
    if (stack.length > 0) {
      var func = stack.pop();
      func[0].apply(null, func[1]);
    } else {
      if (callback) callback();
    }
  }

  function mergeSortRecursive(left, right) {
    if (left < right) {
      var middle = Math.floor((left + right) / 2);

      stack.push([merge, [left, middle, right]]);
      stack.push([mergeSortRecursive, [middle + 1, right]]);
      stack.push([mergeSortRecursive, [left, middle]]);
    }
    executeFromStack();
  }

  function merge(left, middle, right) {
    var l = left;
    var r = middle + 1;
    (function mergeWhileLoop() {
      setTimeout(function() {
        if (compare(array, l, r) <= 0) {
          l++;
          if (l <= middle && r <= right) mergeWhileLoop();
          else executeFromStack();
        } else {
          setTimeout(function() {
            var tmp = read(array, r);
            (function mergeForLoop(j) {
              setTimeout(function() {
                var tmp2 = read(array, j - 1);
                setTimeout(function() {
                  write(array, j, tmp2);
                  if (--j > l) {
                    mergeForLoop(j);
                  } else {
                    setTimeout(function() {
                      write(array, j, tmp);
                      middle++;
                      r++;
                      if (l <= middle && r <= right) mergeWhileLoop();
                      else executeFromStack();
                    }, delay);
                  }
                }, delay);
              }, delay);
            })(r);
          }, delay);
        }
      }, delay);
    })();
  }

  mergeSortRecursive(0, array.length - 1);
}
```

...but enough technical stuff. Just have fun with it! I would personally recommend Quicksort on the "Dark" pitch set, or, if you've got some time, Stooge sort on the "Shifting" pitch set.
