Which world most important algorithms have contributed most to humankind in past decades?

I thought this is a good general knowledge for a developer to know about.

If possible, please keep the answer to a specific programming algorithm.
I would like to get a list of the most important ones, only one algorithm per answer.
Please consider to state why the algorithm is significant and important...

  • 2
    It's being closed because (so far) four people consider it "not a real question", probably because we don't have any real idea what, in isolation, an important programming algorithm is. – David Thornley Nov 19 '10 at 21:40
  • 2
    It might be off-topic, but its a real question. – Jeremy Nov 19 '10 at 22:32
  • 1
    +1 Good question. I suggest re-asking this on cstheory.stackexchange.com – Aleksandr Levchuk Nov 21 '10 at 7:46
  • 1
    Why do you answer your own questions? Several times? – user1249 Nov 26 '10 at 21:04
  • 2
    No wrong answers + unlimited number of answers + an unambiguous comment asking for "one per answer" + author posts several of his own answers = textbook case of a non-constructive question. I know it's old, but let's please close this. – Aaronaught May 27 '11 at 21:17

28 Answers 28


Public/private key encryption is pretty darn important. Internet commerce would be nowhere as ubiquitous without it.

  • 4
    +1 and to add to your answer, RSA. – sange Nov 19 '10 at 20:45
  • There's a whole group of algorithms and best-practices involved in turning cryptographic codes (like RSA) into practical solutions. – Donal Fellows May 28 '11 at 11:26

Dijkstra's algorithm

The algorithm exist in every router in the world, for identifying the best route between two nodes in a network.

  • Are you sure? Most routers either know that the IP-number belongs to it and forwards it to the machine on the local network, or know a router who know better - the default router - in which case the packet goes to that router. Big routers may know that for IP-address range X1-Y1 the packet should go to router R1, for range X2-Y2 the packet should go to router R2, etc. There is no Dijkstras algorithm involved in this. – user1249 Nov 19 '10 at 23:41
  • 2
    @Thorbjørn Ravn Andersen: But for the router to know that information, someone at some point would have had to use Dijkstra's algorithm. Yes, it's not used for actually routing each individual packet, but it is used in determining routing tables on big networks. +1. – Billy ONeal Nov 20 '10 at 1:06
  • @Billy, where exactly would you expect that the Dijkstra algorithm is actually used and by whom? – user1249 Nov 20 '10 at 7:19
  • @Thorbjørn Ravn Andersen: To my understanding, it plays a role in OSPF, which is the foundation of choosing the correct routes for small networks. Connections between larger networks use BGP, which is more policy based. I'm not sure if BGP uses Dijkstra's algorithm or not. – Billy ONeal Nov 20 '10 at 15:59
  • 3
    @Billy, but my objection was to "exists in EVERY router in the world". That is - in my opinion - plainly wrong. – user1249 Nov 26 '10 at 21:05

Fast Fourier transform (FFT)

The FFT is an extremely important and widely-used method of extracting useful information from sampled signals.

A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse.

  • 4
    I had a boss once who, decades earlier, had written a series of FFT functions for the PDP-11. He sold a deck of punchcards with those functions with an ad in the back of Popular Science, and made pretty serious bank. Evidently he had people using his code for everything from signal processing to stock market prediction. – Dan Ray Nov 24 '10 at 13:10


PageRank is a link analysis algorithm, named after Larry Page, used by the Google Internet search engine that assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set.

  • haha, our answers were just 2 seconds apart,sorry :) – Maksee Nov 19 '10 at 20:48
  • no problem at all! :) – Amir Rezaei Nov 19 '10 at 21:00
  • 36
    I never realized it was named after Larry Page. I always assumed the name had something to do with Web Pages. – JohnFx Nov 19 '10 at 21:56
  • 1
    @JohnFx Whoa, no kidding! – Mark C Nov 19 '10 at 22:05
  • +1: but can it qualify if the actual algorithm isn't known to humankind? (IIRC wikipedia's is an approximation) – Steven Evers Nov 21 '10 at 1:52

Data compression algorithms

In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use, through use of specific encoding schemes.

  • 2
    Exactly and I think the basic compression algorithm LZW can be considered one of the most beautiful algorithms in software engineering. – mojuba Nov 20 '10 at 16:10
  • "if possible give the name of the specific algorithm" – user1249 Dec 17 '10 at 18:59

Smith-Waterman (and Needleman-Wunsch)

This may be too far fetched so please comment.

Smith-Waterman: The Sequence Alignment Algorithm

I think one of such examples is the Smith-Waterman and Needleman-Wunsch algorithms and their approximations. All of them are essentially doing the same thing: they align two or more strings (sequences). There is a significance in Biology. When DNA or Protein sequences are aligned - regions of structural, functional and evolutionary similarity are revealed.

BLAST as a descendant of Smith-Waterman

A heuristic that approximates Smith-Waterman is BLAST. It allows searching sequences of large databases for Biological similarity. The popularity of BLAST is really great - it's very likely the most widely used algorithm in Biology. The newer areas in Bioinformatics and Genomics have newer and better approximations of Smith-Waterman/Needleman-Wunsch algorithms that are more accurate than BLAST.

Genome Assembly as a descendant of Smith-Waterman

High-throughput approximations of Smith-Waterman and Needleman-Wunsch that are faster than BLAST are used to assemble Genomes from shotgun sequencing - where the product of the sequencer machine is a huge amount DNA reads (billions) from arbitrary parts of the Genome that are very short (50 to 100 nucleotides). The approach was used to complete the Human Genome Project. All modern sequencing is done this way.

Multiple Sequence Alignment an extension of Smith-Waterman

Numerous Multiple Sequence Alignment algorithms exist - they are approximating a multi-sequence version of the Smith-Waterman/Needleman-Wunsch. Multiple sequences are aligned as a group simultaneously to each other. It's a much harder problem than it's pairwise counterpart, but the solutions provide much more insight into Biological function, structure, and evolutionary history of related sequences.

  • Hello and welcome to Programmers! You might want to break up this answer into one for each of the algorithms you're presenting here as per it is customary for list questions like this to facilitate voting and sorting. – Yi Jiang Nov 20 '10 at 10:28
  • @Yi Jiang: My pantheon! I misread your comment as "facilitate vomiting". :-/ – dr Hannibal Lecter Nov 20 '10 at 12:14
  • Here I argue for only one algorithm - Smith-Waterman (and it's variant Needleman-Wunsch) – Aleksandr Levchuk Nov 20 '10 at 22:28

Siam named the following as the most important algorithms of the 20th century:

1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly.

1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making.

1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation.

1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra.

1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code.

1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical.

1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases.

1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components.

1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers.

1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding.

Personally I would replace Integer Relation Detection with PageRank.


PageRank, love it or hate it, but it affects decisions and actions of millions people worldwide googling on a daily basis.


If I had to list the top 3 most important algorithms in use today in computers, I would say:

  1. Binary Search
  2. Quicksort
  3. Dijkstra's algorithm

The Binary Search algorithm is used constantly to narrow down on an item within a sorted list, most index lookups will use something along these lines at some point. This algorithm provides a search of an ordered list in o(log n) time.

The Quicksort algorithm finally managed to get sort down to O(n log n) average case and O(n^2) worse case. Sorting is one of the most common data tasks in a computer and one of the most expensive, improving the average case sort was a huge step forward in efficiency.

Dijkstra's algorithm as has been said produces a shortest path between points within a graph. This is used widely for all manner of routing applications, most extensively with regard to the internet itself ensuring that the quickest path through the tangled web of interconnected routers is used.

  • Binary search would have to be very, very old... I mean, it was formulated 'in the past' and it was in a 'decade', but it would have been around for many hundreds of years. – Kirk Broadhurst Feb 13 '11 at 9:57
  • @Kirk Broadhurst: Still, it is an incredibly important algorithm for computers. Regardless of when a human first conceived it. – Orbling Feb 13 '11 at 13:39

Bayes' Theorem

It has probably contributed the most to keeping the amount of time-wasting spam in my inbox to a manageable level.

Of course, I'm it has been used in numerous other worthwhile applications, but SPAM-killing is my favorite.

  • I would give you thumb up, but this is a theorem (one of the best) and not an algorithm. However many algorithms are based on this theorem. – Amir Rezaei Nov 19 '10 at 21:56
  • I was just trying to lump them all into a general category of algorithms, but technically you are correct. – JohnFx Nov 19 '10 at 21:58
  • @AmirR Technically correct, the best kind of correct! – Mark C Nov 19 '10 at 22:02


This is the sorting algorithm now used in Python, Java 7 and Android


  • O(N log N) worst case (does not degenerate)
  • O(N) for almost sorted list (in fact N-1 exactly on already sorted list)

And the beauty of it ? It's stable! And therefore suitable for multipass sorting according to various criterion.

By the way, if anyone has an optimized C++ implementation on hand...

  • It can't be Θ(NlogN), as it has that better behavior on an already sorted list. O(NlogN) is the right notation here. – Donal Fellows May 28 '11 at 11:30
  • While this one is nice, I'd certainly not call it "one of the greatest algorithms invented in the past decades". Mergesort, upon which Timsort is based, is the real achievement. – Billy ONeal May 29 '11 at 7:03

All algorithms which used for solving Visibility Problem in 3D Computer Animation seems crucial to me.

Painter's algorithm

The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics. When projecting a 3D scene onto a 2D plane, it is necessary at some point to decide which polygons are visible, and which are hidden.


In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional (3-D) graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which are hidden. The painter's algorithm is another common solution which, though less efficient, can also handle non-opaque scene elements. Z-buffering is also known as depth buffering.

Hidden surface determination

In 3D computer graphics, hidden surface determination (also known as hidden surface removal (HSR), occlusion culling (OC) or visible surface determination (VSD) is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. The analogue for line rendering is hidden line removal. Hidden surface determination is necessary to render an image correctly, so that one cannot look through walls in virtual reality, for example.


Whichever one you need to solve your current problem.

  • 1
    That's what I was going to say. Now I don't have to say it. – Robert Harvey Nov 19 '10 at 20:43
  • Whichever is not a good answer. Whichever algorithms are not significant for humankind. – Amir Rezaei Nov 19 '10 at 21:02
  • 6
    This is not a specific algorithm and even if it were it probably isn't important to humankind. – jason Nov 19 '10 at 21:04

Soundex is a phonetic algorithm for indexing names by sound.

  • How did soundex contributed to humankind ? – barjak Nov 21 '10 at 11:10
  • It improved the ability to use natural language, correcting for minor differences in spelling and regional pronunciation. – sal Nov 23 '10 at 15:21

Viterbi algorithm

Originally used to decode convolutional error-correcting codes, it is now used to solve a wide class of recognition problems (ranging from speech recognition to bioinformatics). You can find it in several communication and storage devices.

  • +1 Viterbi algorithm is very important. @[Giacomo Verticale] perhaps you should mention it's relationship to Hidden Markov Models (HMMs). – Aleksandr Levchuk Nov 28 '10 at 5:48


Although it is a more general term than a specific algorithm, I'd mention MP3 as the aggregation of the different algorithms and techiques which work in cooperation to generate this lossy audio format.

It has surely been very significant in the "digital era".


Runge-Kutta numerical integration. Without it many simulations would not be possible. No space program, no nuclear power, no ballistics, no sports simulations, no bullet proof vests, no crash test simulation, no fluid motion simulation, no chemical interaction simulations, no earthquake resistant buildings ... the list goes on.

  • +1 @j172 I know this one, it's really useful in numerical analysis and simulations. – Amir Rezaei May 28 '11 at 6:19

Sorting algorithm.

  • 5
    this isn't a specific algorithm, though... – Justin L. Nov 20 '10 at 1:05
  • Yeah, what Justin L. said, which sorting algorithm? – dr Hannibal Lecter Nov 20 '10 at 12:09
  • The "Specific algorithm" should be mergesort, the first of the n lg n sorts. – Billy ONeal Nov 20 '10 at 16:03
  • 2
    @dr Hannibal Lecter: Bubble Sort of course. Everything else is premature optimization. – peterchen Nov 20 '10 at 16:12


  • 1
    Yuck! I certainly hope people aren't using quicksort in production code. More importantly mergesort came earlier and is almost as fast. (Hopefully most code uses some variant on Introsort) – Billy ONeal Nov 20 '10 at 1:07
  • 2
    @Billy ONeal, sorting in .NET is all Quicksort. So, any program that calls List<T>.Sort() uses quicksort in production. – Steven Evers Nov 21 '10 at 1:43
  • @SnOrfus: Do you have proof of that statement? To my understanding List<t>.Sort is based on introsort. – Billy ONeal Nov 21 '10 at 1:53
  • 3
    @Billy ONeal: straight from msdn - msdn.microsoft.com/en-us/library/b0zbh7b6.aspx – ysolik Nov 21 '10 at 2:43
  • 3
    @Thorbjørn: It's still not a good general purpose algorithm. Introsort is quicksort, but it switches to heap sort if it goes beyond a given recursion depth. This allows one to have the good characteristics of quicksort but always avoids the pathological cases, even if the algorithm chooses bad pivots. – Billy ONeal Nov 26 '10 at 21:08

Insertion Sort

Easy to implement, very fast on small lists and used in Merge Sort / Quicksort implementations to speed them up. It's stable, and operates in O(n) on sorted lists (when sorted in ascending order).


Gauss-Jordan in matrix computation


Kalman Filter

It gets heavily used in navigation, target tracking (for almost any sensor: radar, sonar, FLIR, ladar). One textbook shows an application in a disk drive controller. Robotic control systems frequently use Kalman filters.


Spoken and Written language.

They are currently one of the most efficient algorithm to transfer knowledge from one thing to another. Without language, civil society could not exist, and information could not be conveyed.

  • 5
    -1: Algorithms can be expressed using natural language, but natural languages are not algorithms. – Steven Evers Nov 21 '10 at 1:47
  • 2
    Would you say compression algorithms are not algorithms then? All language does is compress information that is conveyed from a source to a receptical. It has specific rules that have to be followed (grammar) just like any other algorithm, and it takes an input (your experiences) and produces a different output (knowledge). I fail to see how you could not consider language an algorithm. – Malfist Nov 21 '10 at 15:41
  • It fails all the standard definitions of algorithm on many fronts. – President James K. Polk Dec 21 '10 at 3:42

The heap data structure and its associated algorithms for heap construction and maintenance.

And show some respect for quicksort. Even if it is not always the sort of choice, it is one of the fundamental algorithms in the historical development of computer science, and is a great vehicle for understanding recursion and algorithm analysis. It is beautiful, and yes, I love it.


Indexing algorithms like B-tree,B+-tree,hash index,binary tree index etc. To index huge amount of data.


MapReduce as a way to divide, conquer and parallelize processing of large data sets.


Brute Force Algorithm !

Many people underestimate this brute force algorithm. Actually it is mostly used to solve problems having no pattern. I love it much!

  • 5
    That's not an algorithm. It's a kind of algorithms. – Adam Lear Dec 16 '10 at 16:32
  • It's a method for breaking encryption. – Amir Rezaei Dec 21 '10 at 7:14
  • I think it is also categorized as an algorithm. "Start from x to y do something." <--- algorithm right? – xport Dec 21 '10 at 7:38
  • An algorithm is a series of steps to accomplish a specific task. That isn't specific. – Anto May 25 '11 at 18:35

Bubble Sort !

Bubble sort is not as bad as Bogosort. That is why I vote for the Bubble sort.

  • 1
    Please consider to state why the algorithm is significant and important, people seem to just disagree over why Bubble Sort might be significant and important. – Tamara Wijsman Dec 20 '10 at 22:17
  • 5
    Even Barack Obama knows bubble sort is the wrong way to go. – Joey Adams Dec 21 '10 at 3:11
  • @TomWij, @Joey: see my update. – xport May 29 '11 at 3:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.