TutorialKart.comSorting Algorithms
Sorting algorithms arrange the elements of a list or array in a required order, such as ascending numerical order, descending numerical order, or alphabetical order. The order is decided by a comparison rule: for numbers it may be the numeric value, and for words it may be lexicographical order.
Sorting is used before searching, ranking, merging records, removing duplicates, preparing reports, and displaying data in a readable order. Different sorting algorithms solve the same basic problem, but they differ in speed, memory usage, stability, and simplicity.
Sorting algorithms for numbers, strings, and records
A sorting algorithm does not depend only on the data type. It depends on the key used for comparison. The key is the value by which each item is ordered.
- Numerical Sorting – elements in the list or array are numbers. Following are some of the numerical sorting algorithms.
– Bubble Sort
– Insertion Sort
– Selection Sort
– Heap Sort
– Merge Sort - Lexicographical Sorting – elements in the list or array are words (like in a dictionary or phone book).
The same idea also applies to records. For example, a list of students can be sorted by roll number, name, total marks, or date of admission. In such cases, the sorting algorithm compares only the selected key while moving the whole record.
Important properties used to compare sorting algorithms
Sorting Algorithms could be categorized on the basis of how they are done, resources they use, number of computations they require and so on. Before choosing one, check these properties.
- Time complexity: how the running time grows when the number of elements grows.
- Space complexity: how much extra memory the algorithm needs.
- Stability: whether equal elements keep their original relative order.
- In-place behavior: whether the algorithm sorts mainly inside the given array instead of creating another large array.
- Adaptiveness: whether the algorithm becomes faster when the input is already partly sorted.
In-place sorting algorithms
An in-place sorting algorithm rearranges elements mostly within the original array or list. It uses only a small amount of extra memory compared with the input size. Bubble sort, selection sort, insertion sort, and heap sort are common examples of in-place sorting algorithms.
For example, if an array is sorted by repeatedly swapping elements inside the same array, the algorithm is usually considered in-place. The array object remains the same; only the positions of its elements change.
Not in-place sorting algorithms
A not in-place sorting algorithm needs extra memory that grows with the number of elements. Merge sort is the usual example: it divides the input and uses temporary arrays or lists while merging sorted parts.
Extra memory is not always bad. Algorithms that use extra memory may be easier to make stable, may be faster for large inputs, or may be suitable when the original data should not be modified.
Stable sorting algorithms and duplicate elements
A stable sorting algorithm preserves the relative order of equal elements. This matters when the items contain more information than the key being sorted.
Suppose two students have the same marks. If the list was already arranged by name and then sorted by marks using a stable sort, students with the same marks remain in name order. Bubble sort, insertion sort, and merge sort are stable when implemented in the standard way.
Not stable sorting algorithms and equal-key records
A not stable sorting algorithm may change the relative order of elements that compare as equal. This does not mean the algorithm runs forever. It only means that equal-key records may be rearranged while sorting.
Selection sort, heap sort, and the usual in-place quick sort are not stable in their common implementations. Stability can sometimes be added, but it may require extra memory or a different implementation.
Common sorting algorithms with time and space complexity
The table below compares widely used sorting algorithms. Here, n is the number of elements, k is the range of integer keys, and d is the number of digits or passes used by radix sort.
| Sorting algorithm | Best time | Average time | Worst time | Extra space | Stable? | Best use case |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) with early stop | O(n²) | O(n²) | O(1) | Yes | Learning comparison-based sorting |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Small or nearly sorted arrays |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No, in common implementation | Simple sorting with few swaps |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Large lists where stable sorting is needed |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) average recursion stack | No, in common in-place implementation | Fast general-purpose in-place sorting |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place sorting with guaranteed worst-case time |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes, when implemented with prefix counts | Integer keys in a small known range |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | Yes, when each digit pass is stable | Fixed-length integers or strings |
Bubble sort example in Java
The following Java program sorts an integer array in ascending order using bubble sort. This example is useful for understanding comparisons, swaps, and the early-stop optimization.
import java.util.Arrays;
public class SortingExample {
static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] numbers = {5, 1, 4, 2, 8};
bubbleSort(numbers);
System.out.println(Arrays.toString(numbers));
}
}Output:
[1, 2, 4, 5, 8]How bubble sort works on the sample array
For the input [5, 1, 4, 2, 8], bubble sort repeatedly compares adjacent values and swaps them when they are in the wrong order.
- Compare 5 and 1. Since 5 is greater, swap them:
[1, 5, 4, 2, 8]. - Compare 5 and 4. Swap them:
[1, 4, 5, 2, 8]. - Compare 5 and 2. Swap them:
[1, 4, 2, 5, 8]. - Compare 5 and 8. No swap is needed.
- At the end of the first pass, the largest value, 8, is already at the end.
The next passes repeat the same idea for the unsorted part of the array until no swap is needed.
Which sorting algorithm should you choose?
The best sorting algorithm depends on input size, input order, memory limits, and whether equal-key records must keep their original order.
- For learning: start with bubble sort, selection sort, and insertion sort because their steps are easy to trace.
- For small or nearly sorted input: insertion sort is often a good choice because it can finish quickly when the data is already close to sorted.
- For stable sorting of large data: merge sort is a common choice because its worst-case time is O(n log n) and it is stable.
- For in-place sorting with good average speed: quick sort is commonly used, but its worst-case time depends on pivot choices.
- For guaranteed O(n log n) worst-case time with O(1) extra space: heap sort is suitable, but it is not stable.
- For integer keys in a limited range: counting sort or radix sort may be faster than comparison-based sorting.
Common mistakes while learning sorting algorithms
- Confusing stability with correctness: an unstable sort can still sort correctly; it may only reorder equal elements.
- Ignoring worst-case time: quick sort is fast on average, but poor pivot choices can lead to O(n²) time.
- Calling every low-memory algorithm in-place: strict in-place sorting uses only a small fixed amount of extra storage; recursion stacks and temporary arrays should be counted separately.
- Using bubble sort for large production data: bubble sort is useful for learning, but O(n²) time makes it inefficient for large arrays.
- Forgetting the comparison key: sorting records requires a clear key, such as name, marks, price, or date.
Sorting algorithms FAQ
What are five common sorting algorithms?
Five common sorting algorithms are bubble sort, selection sort, insertion sort, merge sort, and quick sort. Heap sort, counting sort, and radix sort are also commonly studied.
What are seven sorting algorithms used in data structures?
Seven sorting algorithms often covered in data structures are bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, and counting sort. Radix sort is another important non-comparison-based algorithm.
Which sorting algorithm is easiest to understand first?
Bubble sort is usually the easiest to trace because it compares adjacent elements and swaps them when they are in the wrong order. Insertion sort is also beginner-friendly and more useful for nearly sorted data.
Which sorting algorithm is hardest to learn?
There is no fixed hardest sorting algorithm. Many beginners find quick sort harder because of partitioning and recursion, while heap sort can be difficult because it requires understanding the heap data structure.
Is merge sort better than quick sort?
Merge sort is stable and has O(n log n) worst-case time, but it usually needs O(n) extra space. Quick sort is often fast and in-place in common implementations, but its worst-case time is O(n²). The better choice depends on the input and requirements.
Sorting algorithms editorial QA checklist
- Does the tutorial clearly define sorting as arranging elements by a comparison key?
- Are in-place, not in-place, stable, and not stable sorting explained with duplicate-element behavior?
- Are time and space complexities shown with correct notation for each listed sorting algorithm?
- Does the Java code compile and produce the stated sorted array output?
- Do the FAQ answers address common questions about five algorithms, seven algorithms, easiest algorithm, hardest algorithm, and merge sort versus quick sort?
Sorting algorithms summary
Sorting algorithms arrange data in a defined order using a comparison rule or a key. Bubble sort, insertion sort, and selection sort are simple to learn, while merge sort, quick sort, and heap sort are important for larger inputs. To compare sorting algorithms correctly, check time complexity, extra space, stability, and whether the algorithm works in-place.