Merge Sort
"Merge Sort" is a sorting algorithm that breaks down, or divides and conquers, an input array. It does this by dividing the input array into smaller sub-arrays recursively until each sub-array only holds a single element. After this, the sorting algorithm merges (hence the name) the sub-arrays in a way that creates the previously specified desired order. The algorithm does this continuosly until the array reaches its final sorted form.
Time Complexity Merge Sort is reliable due to its consistent and stable time complexity of O(n log n), and is good for large datasets.
Space Complexity Merge Sort's Space Complexity of O(n) means the algorithm requires memory space proportional to the size of the input array, which may be cumbersome if the user is limited in memory space.
Quick Sort
Quick Sort, much like Merge Sort, relies on the division of the input array, but Quick Sort's methodology is much different. Quick Sort utilizes a "pivot partition" strategy to divide the input array. The sorting algorithm starts by selecting a "pivot element" from the input array. After this, the sorting algorthim enters the partitioning phase and fills the left side of the pivot element with elements less than the pivot (creating a new sub-array) and fills the right side of the pivot with elements greater than the pivot (creating another new sub-array). From there, the sorting algorithm recursively applies itself to the newly created sub-arrays on either side of the pivot until the array elements are correctly ordered.
Time Complexity Quick Sort is efficient with one of the best average time complexities of O(n log n). However, the case-by-case efficiency of Quick Sort is heavily reliant on what element is chosen as the pivot (for each individual recursive application). Due to this, Quick Sort has a worst case time complexity of O(n^2), meaning it lacks the consistent stability of Merge Sort.
Space Complexity Quick sort has efficient Space Complexity of O(logn), which makes Quick Sort a good choice in situations of constrained space.
Heap Sort
The Heap Sort algorithm consists of two parts, heap construction and maximum element extraction. The first part in which the heap is placed in an array with the layout of a "complete binary tree". The "complete binary tree" maps the "binary tree structure" into the array indices; each array index represents a node. In the second part, a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array. The heap is updated after each removal to maintain the heap. Once all objects have been removed from the heap, the result is a sorted array. (Transparency: a lot of google was utilized for this explanation)
Time Complexity Heap sort has the advantage of a consistent and stable time complexity of O(n log n). This can help when the dataset is large and the process effiency needs to be consistent and stable.
Space Complexity Heap Sort is what's defined as an "in-place" algorithm, meaning that it doesn't utilize an extraneous data structure. Therefore, its space complexity is O(1), meaning the amount of memory used is constant regardless of the data its processing.