Sorting Algorithms

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. With a time complexity of O(n²), it's inefficient for large datasets but is easy to implement and understand. The algorithm gets its name because smaller elements 'bubble' to the top of the list with each iteration.

The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. Unlike bubble sort, it makes only O(n) swaps, making it useful when write/swap operations are expensive. However, its O(n²) time complexity makes it inefficient for large datasets. Selection sort is not stable, meaning equal elements might not maintain their relative positions.

Insertion sort iterates through an array and at each iteration it removes one element, finds the location where it belongs and inserts it there. While it has an average time complexity of O(n²), it performs exceptionally well on small or nearly-sorted arrays with best-case O(n) performance. Insertion sort is an adaptive, stable, in-place algorithm that works similarly to how people sort playing cards in their hands.

Merge sort is a divide and conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves. With a consistent O(n log n) time complexity regardless of input data, it outperforms simpler algorithms on large datasets. While requiring O(n) auxiliary space for the merging process, it guarantees stability and is particularly efficient for linked lists. Merge sort is often used in external sorting when data doesn't fit in memory.

Quick sort is a divide and conquer algorithm that picks an element as a pivot and partitions the array around the pivot. With an average time complexity of O(n log n) and minimal space requirements, it's typically faster in practice than other O(n log n) algorithms like merge sort. However, it has a worst-case time complexity of O(n²) with poor pivot selection and is not stable. Quick sort is widely used and serves as the foundation for many programming language sorting implementations.

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to build a max-heap and then repeatedly extracts the maximum element. With a guaranteed O(n log n) time complexity regardless of input data and O(1) auxiliary space, it combines many advantages of insertion sort and merge sort. While not stable and slightly slower than quick sort in practice, heap sort provides reliable performance without the risk of worst-case scenarios, making it valuable for systems requiring consistent performance.