Real world examples to decide which sorting algorithm works best

Amey picture Amey · Jun 13, 2012 · Viewed 26.1k times · Source

I am risking this question being closed before i get an answer, but i really do want to know the answer. So here goes.


I am currently trying to learn algorithms, and I am beginning to understand it as such but cannot relate to it.

I understand Time Complexity and Space Complexity. I also do understand some sorting algorithms based on the pseudo code

Sorting algorithms like

  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Quicksort
  5. Mergesort
  6. Heapsort (Some what)

I am also aware of Best Case and Worst Case scenarios(Average case not so much).


Some online relevant references

  • Nice place which shows all the above graphically.
  • This gave me a good understanding as well.

BUT my question is - can some one give me REAL WORLD EXAMPLES where these sorting algorithms are implemented.

Answer

JustinDanielson picture JustinDanielson · Jun 13, 2012

As the number of elements increases, you will use more sophisticated sorting algorithms. The later sorting techniques have a higher initial overhead, so you need a lot of elements to sort to justify that cost. If you only have 10 elements, a bubble or insertion sort will be the much faster than a merge sort, or heapsort.

Space complexity is important to consider for smaller embedded devices like a TV remote, or a cell phone. You don't have enough space to do something like a heapsort on those devices.

Datebases use an external merge sort to sort sets of data that are too large to be loaded entirely into memory. The driving factor in this sort is the reduction in the number of disk I/Os.

Good bubble sort discussion, there are many other factors to consider that contribute to a time and space complexity.

Sorting-Algorithms.com