Blog

TechJedi > Blog > Algorithms > Sorting Algorithms — Choices

Sorting Algorithms — Choices

No Comments

We all know about the standard comparison based sorting algorithms and their time/space complexity. Algorithms like bubble sort, insertion sort, selection sort, quick sort, merge sort, Heap sort operate with a asymptotic lower bound of O(n log n). Also, other unconventional sorting algorithms like Bucket Sort, Counting Sort, Radix Sort run in O(n)

We will not talk about implementation details and complexities of these algorithms. Here we will discuss about various situations/requirements you have to deal with and choosing best algorithm for them.

RequirementAlgorithmRemarks
Given array/list is nearly sortedInsertion sortTime complexity will be ~O(n)
Given array has lot of duplicated elementsCounting sort, Bucket sortTime complexity will be O(n)
Implement with less write operation (flash devices)Selection sortNo.of write operation = O(n)
Data is really huge (Cannot fit in memory)External Merge sortDatabase systems uses these extensively
Need top K sortedModified Heap sortTime complexity will be ~O(n).
Many search engines returning top 10, 20 results
Sorting Linked list (of big structures)Merge sortDatabase index based sort queries uses them
In general (with unknown characteristics of input)Quick sort–
Other Sources:
  1. http://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice
  2. http://www.sorting-algorithms.com/
  3. http://en.wikipedia.org/wiki/Sorting_algorithm
  4. http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Read Similar Blogs:

database Performance

Databases — Running multi-line scripts from command line

In a typical application using Database, it is natural all...
Read More
Security

Google Authenticator

Google Authenticator is a mobile app that provides two-factor authentication...
Read More
AWS Cloud Computing database Security Serverless Virtual Machine

How does Serverless Architecture work?

TL;DR: Serverless removes the architecture responsibilities like hardware provisioning, scaling, and...
Read More
algorithms data structures sorting

Leave a Reply

Courses

Become a Cloud Architect with AWS Certification

Start Date : 24-September-2022
End Date : 27-November-2022
Technology80 Hours10 Weeks
More Details

Data Structure & Algorithms for Interviews

Start Date : 24-September-2022
End Date : 27-November-2022
Technology80 Hours10 Weeks
More Details

Become a Python Developer

Start Date : 13-August-2022
End Date : 11-September-2022
Technology40 Hours5 Weeks
More Details