Tutorialspoint.dev

Know Your Sorting Algorithm | Set 1 (Sorting Weapons used by Programming Languages)

Ever wondered how sort() function we use in C++/Java or sorted() in Python work internally?

Here is a list of all the inbuilt sorting algorithms of different programming languages and the algorithm they use internally.

  1. C’s qsort() – Quicksort

    • Best Case Time Complexity- O(NlogN)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(N2)
    • Auxiliary Space- O(log N)
    • Stable- Depends on the implementation of the comparator function
    • Adaptive- No
  2. C++’s sort() – Introsort (Hybrid of Quicksort, Heap Sort and Insertion Sort)
    • Best Case Time Complexity- O(NlogN)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(NlogN)
    • Auxiliary Space- O(logN)
    • Stable- No
    • Adaptive- No
  3. C++’s stable_sort() – Mergesort
    • Best Case Time Complexity- O(NlogN)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(NlogN)
    • Auxiliary Space- O(N)
    • Stable- Yes
    • Adaptive- Yes
  4. Java 6’s Arrays.sort() – Quicksort
    • Best Case Time Complexity- O(NlogN)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(N2)
    • Auxiliary Space- O(logN)
    • Stable- Depends
    • Adaptive- No
  5. Java 7’s Arrays.sort() – Timsort (Hybrid of Mergesort and Insertion Sort)
    • Best Case Time Complexity- O(N)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(NlogN)
    • Auxiliary Space- O(N)
    • Stable- Yes
    • Adaptive- Yes
  6. Java’s Collections.sort() – Mergesort
    • Best Case Time Complexity- O(NlogN)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(NlogN)
    • Auxiliary Space- O(N)
    • Stable- Yes
    • Adaptive- Yes
  7. Python’s sorted() – Timsort (Hybrid of Mergesort and Insertion Sort)
    • Best Case Time Complexity- O(N)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(NlogN)
    • Auxiliary Space- O(N)
    • Stable- Yes
    • Adaptive- Yes
  8. Python’s sort() – Timsort (Hybrid of Mergesort and Insertion Sort)
    • Best Case Time Complexity- O(N)
    • Average Case Time Complexity- O(NlogN)
    • Worse Case Time Complexity- O(NlogN)
    • Auxiliary Space- O(N)
    • Stable- Yes
    • Adaptive- Yes

In the next sets we will implement Introsort ( C++’s sorting weapon ) and Sleep sort, Gnome Sort and other unconventional sorting algorithms.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter