R Data Structures and Algorithms

Merge sort

Merge sort follows the principle of divide and conquer, wherein the input vector is first divided into two halves, then each half is independently sorted and later merged into a single sorted vector. Its key features are as follows:

• Conceptually simple to understand.
• Asymptotically better performance.
• Empirically lower system runtime.
• Concept of merge – as mentioned earlier, merge is performed on two sorted subvectors (halves). The first element of each subvector is compared, and the smallest is picked up and placed in the first position of the output vector. Subsequently, the picked-up element is removed from its corresponding subvector. This process of first element comparison continues till all the elements in both the subvectors become ...