This video sketches a parallel sorting algorithm, Generalised Regular Sample Sort, which is based on the sequential Quicksort algorithm. I introduce the notion of a loop invariant, to express what a loop in the algorithm actually does. The cost of the five supersteps of the parallel algorithm is analysed using the BSP model, and the final expression is simplified to obtain insight into the efficiency of the algorithm.
This video corresponds to Section 1.8 of the book Parallel Scientific Computation: A Structured Approach Using BSP, Second Edition, by Rob H. Bisseling, Oxford University Press, 2020.
An expanded set of slides, solutions to the homework questions, and software accompanying the book can all be found on my personal book page:
https://webspace.science.uu.nl/~bisse101/Book2/psc2
