Faster LSD Radix Sort

LSD Radix Sort algorithm has been around for a long time with first computer usage in 1950’s and 1960’s to sort punch cards by performing several passes at the stack of cards. It has resurfaced in the last decade with GPUs having hundreds and even thousands of processor with internal local truly random access memories […]

Read more "Faster LSD Radix Sort"

Big-O by a Concrete Example

Computer Scientists develop algorithms for all kinds of tasks, such as sorting numbers, searching the web for information, showing web pages and interacting with them, and so on – thousands of different algorithms. Even a task such as sorting a bunch of numbers, has more than 20 different algorithms. When you need to choose one […]

Read more "Big-O by a Concrete Example"

What We Need Is More Heterogeneity

Current processors offer some variety in the types of computational engines. They consist of multiple identical general purpose cores, embedded multi-core graphics cores (GPUs), and accelerators for video and audio compression. Recently, Intel has integrated Field Programmable Gate Array (FPGA) into the server-class processors, for even more customizable computational flexibility. Modern CPU’s (Intel, AMD, ARM, […]

Read more "What We Need Is More Heterogeneity"

Faster Merge in C# and C++

Merging of two pre-sorted arrays into a single array is a core part of the merge sort algorithm. In this blog I’ll discuss a couple of high performance implementations for a serial merge, and a way to reduce the number of comparisons. static public void Merge(int[] a, Int32 aStart, Int32 aEnd, int[] b, Int32 bStart, […]

Read more "Faster Merge in C# and C++"

Faster Sorting in C#

C# has several built-in algorithms for sorting arrays, lists and other containers. Array.Sort and List.Sort have many variations for sorting full or partial containers, using an algorithm that runs on a single CPU core. The Linq library can also sort containers, using a single CPU core or multiple cores in parallel. These are powerful, flexible, […]

Read more "Faster Sorting in C#"