Discover published sets by community

Merge Sort is a divide and conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge function is key to the algorithm. Time complexity is $O(n \log n)$ in all cases, and space complexity is $O(n)$ due to additional arrays used in the merge step.

Builds a max heap from the input data, then repeatedly extracts the largest element from the heap and replaces it with the last item of the heap followed by readjusting the heap. This process is repeated until the heap is empty. Time complexity is $O(n \log n)$, and space complexity is $O(1)$.

An in-place comparison sort. It starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. This method moves elements to the correct position faster than a simple nearest-neighbor exchange. Time complexity ranges from $O(n)$ to $O(n^2)$ depending on the gap sequence, with a space complexity of $O(1)$.

Quick Sort picks an element as a pivot and partitions the array around the pivot. The pivot splits the array, with all elements less than the pivot to its left and all greater elements to its right. This partitioning is done recursively. Average time complexity is $O(n \log n)$, but in the worst case, it can be $O(n^2)$. Space complexity is $O(\log n)$ on average for the call stack, though it can be $O(n)$ in the worst case.

Builds a sorted array one element at a time by repeatedly taking one element from the input data and inserting it into the correct position in the already-sorted list. Time complexity is $O(n^2)$ for the worst case, and $O(n)$ for the best case when the data is already mostly sorted. Space complexity is $O(1)$.

It divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front of the list, and a sublist of the remaining unsorted items. On each iteration, the smallest (or largest, depending on sorting order) element from the unsorted sublist is selected and moved to the sorted sublist. Time complexity is $O(n^2)$, and space complexity is $O(1)$.

Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed. Time complexity is $O(n^2)$, and space complexity is $O(1)$.

Non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It uses counting sort as a subroutine to sort. Time complexity can be as low as $O(nk)$ where $n$ is the number of elements and $k$ is the digit length of the number. Space complexity is $O(n+k)$.

An integer sorting algorithm that counts the number of objects that have distinct key values, and uses arithmetic to determine the positions of each key value in the output sequence. Its time complexity is $O(n+k)$ where $n$ is the number of elements in the input array and $k$ is the range of input. Space complexity is also $O(n+k)$.