Sorting is important for optimizing many other algorithms like search/merge algorithms which requires input data to be in sorted order.
Introduction to Sorting Algorithms
Carvia Tech | May 19, 2019 | 2 min read | 124 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.
Popular sorting algorithms
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:
- Top 100 interview questions on Data Science & Machine Learning
- Python Flask Interview Questions
- Python coding challenges for interviews
- Google Data Scientist interview questions with answers
- Introduction to SVM, hyperplane, TF-IDF and BoW
- Introduction to Python 3.6 & Jupyter Notebook
- Introduction to regression, correlation, multi collinearity and 99th percentile
Find more on this topic:

Machine Learning
Data science, machine learning, python, R, big data, spark, the Jupyter notebook, and much more
Last updated 1 week ago
Recommended books for interview preparation:
Similar Posts
- Installing PySpark with Jupyter notebook on Ubuntu 18.04 LTS
- Send email with attachment in Python
- Send rich text multimedia email in Python
- Blueprints in Flask API Development
- Singleton Design Pattern in Python
- SVM after LSTM deep learning model for text classification
- RuntimeError: get_session is not available when using TensorFlow 2.0
- Deploying Keras Model in Production with TensorFlow 2.0
- Python coding challenges for interviews
- Python Flask Interview Questions
Enter your email address to subscribe to this blog and receive notifications of new posts by email.