Let us first discuss about merge sort.
Merge sort is a stable sorting algorithm. Stability in sorting algorithms means that two equal elements retain their relative positions after sorting. Merge sort achieves this by ensuring that when two elements are compared and found to be equal, the algorithm does not change their order in the merged array. This is particularly useful when the data has multiple fields and the sorting is performed based on one of these fields while preserving the relative order of equal elements.
Merge sort is not an in-place sorting algorithm. An in-place algorithm sorts the elements within the original data structure using only a constant amount of extra space. Merge sort, however, requires additional space proportional to the size of the array being sorted because it creates temporary arrays for merging. The space complexity of merge sort is 𝑂(𝑛)O(n), where 𝑛n is the number of elements in the array.
Now, let us discuss about insertion sort.
insertion sort is a stable sorting algorithm. As elements are inserted into their correct positions, the algorithm ensures that equal elements retain their relative order. This stability is achieved because when inserting an element into its proper position, the algorithm shifts all larger elements one position to the right, preserving the relative order of equal elements.
Insertion sort is an in-place sorting algorithm. It sorts the array within the original data structure using a small, constant amount of extra space. The algorithm only requires a few additional memory locations for temporary variables used during the insertion process. Thus, its space complexity is O(1), which qualifies it as an in-place algorithm.