Biggest Challenge & What I Learned

• First WASM Project

  This project was made twice. First, as a way to get into Rust/Bevy. Second, with wasm as a primary consideration, which I had thought at the start required no multi-threading (which I had in the first build).

  The first project taught me multi-threading (e.g., dealing with Arc's, Mutex's, locks, atomic types, threads, etc.). At most, the current rendition of the program only uses MPSC channels for loading in user-selected audio in web builds.

  The main difference: in the first version, multi-threading felt necessary since the sorting algorithms were done in loops, which of course blocked the main thread (e.g., could not rotate camera while sorting was running). The sorting algorithms were put in their own thread, which freed up interactivity for the rest of the program. I thought Web/Wasm targets did not allow multiple threads, and as such, the program was made again with incremental versions of the sorting algorithms, and then were called many times per frame depending on a modifiable frame budget variable (e.g., if frame budget was 4ms, sorting would increment as many times as it could in those 4ms) so nothing was blocked and everything could run on the web since multiple threads were not used.

  I now realize that wasm and modern web browsers can support multiple threads, and even though bevy (as of the time of writing this) is still experimenting with supporting it , I believe that given all I've learned working on this, I could write this program a third time and have parallel sorting on both native and web builds.

  The experience gained from working on the first version made the second version far better and development ran smoother as I had already gained experience working with Rust/Bevy, and all I had to learn was wasm and rust-wasm bindings, which were relatively easier in comparison.

• Swap-Based Merge Sort

  This program currently only visualizes swap-based algorithms as they are the easiest to visualize. Traditionally, merge sort is not swap-based, but it can be made to be swap-based as detailed below. I essentially made this up myself and if there are online resources that describe this same method, I did not utilize them at all. Of course the source code is available but this gives a rough overview of how it is done.

  Fundamentally, merge sort builds a "K" array by comparing elements between 2 split arrays and simply iterating through them until all the elements are placed inside the "K" array in order. At first, the 2 arrays are just the size of 1, so the "K" array being built is of size 2. Then the 2 arrays have the size of 2, and so the size of "K" array is 4, and so on until "K" is the size of the entire input list, which will, at that point, be an ordered/sorted list. For a more detailed explanation, consider a more focussed overview of the subject matter.

  The way this program makes merge sort be swap-based is by tracking where elements of the "left" array go after being swapped. For example, imagine that the input is currently "2, 5, 6, 10, 1, 3, 4, 7, 8, 9", the 2 arrays are of size 4, and the "K" array needs to be of size 8 before the next loop around, but starts at 0. Elements 0-3 are in Left Array ("2, 5, 6, 10") and elements 4-8 are in Right Array ("1, 3, 4, 7"). We begin comparing element-by-element: "2" from Left Array is bigger than "1" from Right Array, so it gets swapped with the element at "K" index, currently at "2". Now the input looks like this: "1, 5, 6, 10, 2, 3, 4, 7, 8, 9." For the next comparison, K increments to a 1, Right Array increments to point to its next element "3". Since Left Array must still point to "2" for future comparisons, it updates where it is pointing to. It does so by putting its element's new position/index into a queue, or a VecDeque in Rust. This is the gist of it, whenever Right Array swaps with a element in the Left Array, it simply adds that element's new index into the queue to track it for later comparisons. They are removed from the queue when they are smaller in a comparison and swap places with wherever the "K" index is at that comparison. There is only one more important aspect to be aware of.

  There are cases where an element's position in the queue has to be updated. For example, say that the input is currently "1, 2, 3, 4, 5, 6, 10, 7, 8, 9", K is currently at a 6, Left Array is pointing at "10" (which is at the 6th index) and Right Array is pointing at "7". "7" is smaller than "10", so we swap. Right Array increments, and importantly, because the position of the element in Left Array's queue has changed ("10" was at 6, but now is at 7), we update the element in the queue to point to its new location. At the end, the input looks like this: "1, 2, 3, 4, 5, 6, 7, 10, 8, 9." With Left Array still pointing at 10. So, ultimately, Left Array simply uses a queue to keep track of where its next elements go for future comparisons and updates their positions if required. With this, you can do merge sort with only swaps.