Sorting Algorithms
How does a computer put a list in order?
Summary
A computer cannot "see" the sorted version of a list of numbers; at each step it can only compare two elements and make a decision. Sorting algorithms choose those comparisons with different strategies. Some are simple but slow, while others split and merge cleverly and finish the same job in far fewer steps.
In depth
Sorting is one of the most studied problems in computer science: search engines, databases, spreadsheets and social media feeds are constantly putting things in order. Bubble, selection and insertion sort compare elements one by one, and their work grows roughly as n² as the list gets longer. Merge sort (John von Neumann, 1945) and quicksort (Tony Hoare, 1959) use a "divide and conquer" strategy to bring this down to n log n. The difference hardly matters for short lists, but with millions of elements it is the difference between seconds and hours. Which algorithm is best also depends on the data itself: on a nearly sorted list, simple insertion sort can beat quicksort.
Rate Sorting Algorithms
What did you think of this content? Click the stars to leave your rating.
Leave a Comment and Rating
Sign in to comment and rate. Membership is free.