Most algorithms books describe LSD and MSD Radix Sort variations. However, they do not cover in-place variations. Wikipedia does not describe it either. In this blog I describe an in-place MSD Radix Sort. This is a simpler variant to describe than the type I’ve developed and discussed in previous blogs and in my “Practical Parallel […]
Read more "In-Place MSD Radix Sort Explained"I’ve been optimizing variety of Radix algorithms for over a decade: LSD and MSD Radix Sort, Single Core and Multi-Core, and Radix Selection. Several of these optimization techniques can be applied to all of these algorithms. In this blog, I’ll discuss each of these optimizations and show how much performance is gained, for sequential single […]
Read more "Fastest LSD Radix Sort in C++ on a Single CPU Core"There is a closely related algorithm to sorting called Selection, which provides the k-th element from an unsorted array. For example, a 17-th highest test score from a college Physics class, or a 91-st most popular book at the library. One way to accomplish Selection is to sort the array and then access the k-th […]
Read more "Radix Selection Algorithm"Parallel programming frameworks like C++ Threading Building Blocks (TBB) and C# Task Parallel Library (TPL) are good at handling large work items using multi-core processors. Both provide mechanisms to break a large problem into smaller pieces (grains), to provide work for multiple cores in parallel, gaining performance acceleration. With 20-core laptops widely available along with […]
Read more "Parallel Pattern of Bundling Small Work Items"
Algorithm Performance 