# Publication: Engineering Parallel String Sorting in Algorithmica Journal

Posted on 2015-09-22 15:46 by Timo Bingmann at Permlink with 0 Comments. Tags: research sorting university

Our paper "Engineering Parallel String Sorting" was accepted for publication in Springer's Algorithmica Journal, and is available online at http://dx.doi.org/10.1007/s00453-015-0071-1.

Compare to our older technical report, the journal edition contains many (minor and major) corrections, additional references and better explanations.

A pre-print version is available here: Engineering-Parallel-String-Sorting.pdf .

Please refer to the main parallel-string-sorting page for details and source code.

This blog entry continues on the next page ...

# 1.000.000 Views of Sound of Sorting YouTube Video

Posted on 2014-10-26 17:30 by Timo Bingmann at Permlink with 1 Comments. Tags: sorting sound of sorting frontpage

Some time last week my YouTube video "15 Sorting Algorithms in 6 Minutes" reached 1 million views. The original video was uploaded on 2013-05-20 which is just 524 days ago, so on average about every 45.2 seconds someone started to watch the video (which itself is about 6 minutes long). The world is a really big place. Most of the views, however, occured in spikes of interest, as seen in the graph below.

The original video contained only 15 algorithms. The program "Sound of Sorting" itself, which was used to create the animations, now contains 30 algorithms or variants. For some of the additional algorithms I also created videos on YouTube, which are also worthwhile watching.

There are two parallel algorithms based on sorting networks, where each left-to-right sweep is one parallel sorting step:

An algorithm, which is optimal in terms of the number of writes to sort the array:

An adaptive sorting algorithm which detects presorted areas, and is used in many modern programming language runtime libraries:

An in-place stable mergesort with O(1) extra space:

And two algorithms, that have a high asymptotic worst-case complexity, and are thus more a joke, but still pretty to watch:

This blog entry continues on the next page ...

# Released parallel-string-sorting 0.6 including Parallel Super Scalar String Sample Sort and Parallel Multiway LCP-Mergesort

Posted on 2014-03-09 10:20 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ parallel-string-sorting sorting

This short post announces the second public version of our parallel string sorting project. It is a test framework and algorithm collection containing most sequential and parallel string sorting implementations.

The collection includes parallel super scalar string sample sort (pS5), which we developed and showed to have the highest parallel speedups on modern single-socket multi-core shared memory systems. Additionally, the collection now contains parallel multiway LCP-mergesort, which can be used to speed up string sorting on NUMA multi-socket machines.

See the parallel-string-sorting project page for our technical report and more information about version 0.6.

# Sound of Sorting: Viral Video on KIT Informatik Webpage

Posted on 2013-10-24 22:45 by Timo Bingmann at Permlink with 0 Comments. Tags: fun sorting sound of sorting frontpage

Little did I expect what would happen when coding the Sound of Sorting demo program. The initial motivation was to create a program that counts the number of comparisons of sorting algorithms, so that the students in our lecture "Algorithms 1" could compare the results of theoretical analysis and real implementations. There were many programs similar to the one I finally made, but there was no program in which the sorting algorithms were easily readable, and not entwined with visualization code. I needed the third-year students to see "simple" code and at the same time have comparison counting and nice visualizations. And none of the existing programs highlighted the internal workings of the algorithms well.

These were the initial goals what became the Sound of Sorting. The program itself took only about seven days of coding work, which was done from the 17th to 21st of May this year. The program had to be finished for the lecture on the 22nd, so there was a hard deadline to meet. The videos were created on the following weekends, and additional algorithms were added later.

Adding sound effects was very much an afterthought, because I had done some similar work previously with manipulating waveforms. Thus there was no learning curve to overcome to have comparisons play sounds. What kind of sound to play, however, needed a lot of artistic touch, trial and error, and the ability to map and transform frequency, oscillators and envelopes as needed. Forming, mixing and bending sound waves as done in the Sound of Sorting requires a mathematical mindset and some appropriate background.

The by-product of this demo program for teaching sort algorithms was the YouTube video "15 Sorting Algorithms in 6 Minutes" which, to my great surprise, went viral on social networks and was viewed 420.000 times to-date. I'm glad that many people with otherwise no connections to algorithmics find this video interesting, and hope that those with further interest view the slower videos, which provide more insight into the algorithms.

Today, the video infected the front page of my current employer: the Department of Informatics at the Karlsruhe Institute of Technology (KIT), which is of course whom I originally made the demo program for. The text, which I wrote for that occasion, can be viewed in German at the original news article about the viral video (or in the screenshots below). I have translated it into English below, since it contains some further comments about the video.

This blog entry continues on the next page ...

# Published "The Sound of Sorting" 0.6

Posted on 2013-05-22 23:50 by Timo Bingmann at Permlink with 2 Comments. Tags: c++ university fun sorting sound of sorting

This post announces the publication of my demo program for integer string sorting algorithms, called "The Sound of Sorting". It both visualizes the internals of sorting algorithms, and generates sound effects from the values being compared!

The demo is implemented using the cross-platform toolkits wxWidgets and SDL, can be executed on Windows, Linux and Mac, and runs in real time.

There are also many videos of the sorting algorithm on my new YouTube channel.

See the Sound of Sorting project page for the demo program and source code, and more information about version 0.6.

# Released parallel-string-sorting 0.5 including Parallel Super Scalar String Sample Sort

Posted on 2013-05-08 11:47 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ parallel-string-sorting sorting

This short post announces the first public version of our parallel string sorting project. It is a test framework and algorithm collection containing many sequential and parallel string sorting implementations.

The collection includes parallel super scalar string sample sort (pS5), which we developed and showed to have the highest parallel speedups on modern multi-core shared memory systems.

See the parallel-string-sorting project page for our technical report and more information about version 0.5.

Copyright 2005-2019 Timo Bingmann - Impressum