Search code examples
algorithmmergesortpseudocode

Merge step of the Merge sort algorithm

I have a question and I hope someone could help me. I really don't understand the pseudo code of the merge step of the merge sort algorithm. I understand how it works but not the code. Would be grateful if someone could explain it to me:) thanks Merge sort pseudocode Merge step pseudocode

I implemented the code but I did not understand it.

Solution

  • n2 and n2 are lengths of input subarrays - they are calculated using left-middle-right indices

    Infinity value is used as sentinel to stop when you reach array end, also to get rid off separate copying of array tails (when one array is exhausted)

    Note this is mostly impractical, and in reality merge implementation often checks whether index of corresponding array is beyond the limits:

    while i<=n1 and j<=n2:
   if L[i] <= R[j]: 
        A[k++] = L[i++]
   else:
        A[k++] = R[j++]

    then move the rest:

    while i<=n1:
    A[k++] = L[i++]
while j<=n2:
    A[k++] = R[j++]