1. The "Skew Algorithm", aka "DC3", aka Kärkkäinen-Sanders. It uses radix sort in an extremely brilliant way to construct suffix arrays in linear time. I found these explanations helpful (though it still took me some time to digest): http://www.mi.fu-berlin.de/wiki/pub/ABI/SS13Lecture3Material...2. Fast Fourier transform (FFT). It's another quite brilliant algorithm used for decomposing a function into its frequency components in linearithmic time (among other things).

 I would also vote for FFT. It's amazing how widely it's used and what sort of tricks you can do in frequency domain. Multiplying polynomials? Simple! Multiple 2D projections of a 3D object? Just FFT them, do a couple of simple steps and you will get a 3D model.
 Do you have some details for these applications ?
 The multiplication is concisely described here http://numbers.computation.free.fr/Constants/Algorithms/fft....For 2D -> 3D, see https://en.wikipedia.org/wiki/Projection-slice_theorem for a simple overview

Search: