Sorting Algorithms

Comparison-Based Sorting Algorithms

These algorithms sort the elements by comparing them to one another.

1. Bubble Sort

Idea: Repeatedly step through the list, compare adjacent elements, and swap them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Complexity: Time: O(n²) | Space: O(1)

Use Case: Mostly educational. It's too slow for most real-world applications.

2. Selection Sort

Idea: Repeatedly find the minimum element from the unsorted part of the array and put it at the beginning.

Complexity: Time: O(n²) | Space: O(1)

Use Case: Simple to understand. It has the advantage of making at most O(n) swaps, which can be useful if write operations are expensive.

3. Insertion Sort

Idea: Build the final sorted array one item at a time. It iterates through the input elements and inserts each element into its correct position in the sorted part of the array.

Complexity: Time: O(n²) worst-case, O(n) best-case (for nearly sorted data) | Space: O(1)

Use Case: Very efficient for small or nearly sorted datasets.

4. Merge Sort

Idea: A "divide and conquer" algorithm. It divides the array into two halves, recursively sorts them, and then merges the two sorted halves.

Complexity: Time: O(n log n) | Space: O(n)

Use Case: Very reliable and efficient. Its guaranteed O(n log n) performance makes it a popular choice. Its main drawback is the extra space it requires.

5. Quick Sort

Idea: Another "divide and conquer" algorithm. It picks a 'pivot' element and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Complexity: Time: O(n log n) on average, O(n²) worst-case | Space: O(log n) on average

Use Case: Often faster in practice than Merge Sort due to better cache performance and in-place sorting. The worst-case can be avoided with a good pivot selection strategy.

Visualize the Algorithms

To better understand these algorithms, use the interactive simulation below. It helps build a strong mental model of how each one operates.