Introduction to Sorting Algorithms

Upasana | May 19, 2019 | 2 min read | 468 views


Sorting is ordering a list of objects in a certain order. Input data is often stored in an array, which allows random access, rather than a list, which only allows sequential access.

Use of sorting algorithms

Sorting is important for optimizing many other algorithms like search/merge algorithms which requires input data to be in sorted order.

Most popular sorting algorithms include:

  • Bubble sort

  • Insertion sort

  • Quick sort

  • Heap sort

  • Radix sort

  • Selection sort

  • Merge sort

  • External Merge sort

Most commonly used algorithms are heap sort, merge sort and quick sort with average time complexity of O(n log n).

Quicksort

Quicksort is essentially a divide and conquer algorithm which relies on a partition operation. To partition an array, a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. The lesser and greater sublists are then recursively sorted. The average time complexity of quicksort is O(n log n) and space complexity is O(log n). It is one of the most popular sorting algorithm and its implementation is available in most standard programming libraries.

External Merge Sort

external merge sort is used when the input data can not fit into the main memory (usually RAM) and instead it must reside in the slower external memory, usually hard disk drive.

Merge Sort

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4…​) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.

Bubble sort

Bubble sort starts at the beginning of the data set. It compares the first two elements and if the first element is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of tje data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. Average and worst time complexity of this algorithm is O(n2), so it is rarely used for sorting large data sets.


Top articles in this category:
  1. Google Data Scientist interview questions with answers
  2. Top 100 interview questions on Data Science & Machine Learning
  3. Flask Interview Questions
  4. Introduction to SVM, hyperplane, TF-IDF and BoW
  5. Python coding challenges for interviews
  6. Introduction to Python 3.6 & Jupyter Notebook
  7. Connect to MySQL with Python 3.x and get Pandas Dataframe

Recommended books for interview preparation:

Find more on this topic: