Sorting is the process of arranging a list of items (like numbers or words) into a specific order, such as ascending (smallest to largest) or descending (largest to smallest). It is a fundamental operation in computer science, used for efficient searching, merging, and data analysis.
Complexity measures how the performance of an algorithm scales with the size of its input \(N\). This is usually expressed using Big O notation (\(O\)).
Measures the number of operations an algorithm performs relative to \(N\). It helps estimate how much time an algorithm will take as the input grows. For example:
Measures the amount of extra memory (beyond the input array itself) an algorithm needs to execute. This is critical for systems with limited memory.
Note on Auxiliary Space Display: The value shown (e.g., \(O(1)\)) is the theoretical worst-case complexity, not a live memory measurement. We display this theoretical value because calculating accurate, real-time memory usage in a browser is impractical; the Big O notation is the standard, educational way to measure an algorithm's space efficiency.
How it Works: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass-through process is repeated until no swaps are needed, meaning the list is sorted.
Key Feature: Largest elements "bubble up" to their correct position at the end of each pass.
How it Works: Divides the array into a sorted part (on the left) and an unsorted part (on the right). It repeatedly finds the smallest element from the unsorted section and places it at the end of the sorted section.
Key Feature: Performs a minimum number of swaps compared to other \(O(N^2)\) sorts.
How it Works: Builds the final sorted array one item at a time. It iterates, taking one element and inserting it into its correct position within the already sorted portion of the array.
Key Feature: Very efficient for small or nearly sorted arrays.
How it Works: A Divide and Conquer algorithm. It selects 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 recursively sorted.
Key Feature: Generally the fastest practical sort, but its worst-case is \(O(N^2)\).
How it Works: A Divide and Conquer algorithm. It continuously splits the array into halves until it has many sub-arrays of size 1 (which are sorted by definition). It then repeatedly merges the sub-arrays to produce new sorted sub-arrays until the whole array is sorted.
Key Feature: Guaranteed \(O(N \log N)\) time complexity and is a stable sort.
How it Works: Uses the Binary Heap data structure. It first converts the array into a Max Heap (where the largest element is the root). It then repeatedly extracts the maximum element from the heap and places it at the end of the array, then re-heapifies the remaining elements.
Key Feature: An in-place sort with guaranteed \(O(N \log N)\) time complexity.