3. How do Insertion sort, Heapsort, Quicksort, and Merge sort work?
By: Chrysanthus Date Published: 13 Oct 2025
Solution
Insertion Sort
Insertion sort takes elements of the array sequentially, and maintains a sorted subarray to the left of the current point. It does this by taking an element, finding its correct position in the sorted array, and shifting all following elements by 1, leaving a space for the element to be inserted.Heapsort
Heapsort builds a binary heap. A binary max heap is a nearly complete binary tree in which each parent node is larger or equal to its children. The heap is formed by sifting elements up in the given binary tree (given array). The heap is stored in the same memory in which the original array elements were. Once the heap is formed, that is binary max heap. The opposite is binary min heap.Quicksort
The Quick Sort algorithm is notable for its approach to sorting an array. Quick Sort begins by selecting a pivot from the provided list, then separates the remaining elements into two groups - those less than the pivot and those greater than it, keeping their order in the initial array. This process is replicated recursively until the entire list is sorted.Merge Sort
Merge Sort recursively halves the given array. Once the subarrays reach trivial length, merging begins. Merging takes the smallest element between two adjacent subarrays and repeats that step until all elements are taken, resulting in a sorted subarray. The process is repeated on pairs of adjacent subarrays until we arrive at the starting array, but sorted.