2. Merge Sort #

Created Wednesday 01 January 2020

• Is a head recursion.
• We need merge() and mergeSort()
• We do it on two halves.
• pseudo code

void mergeSort(arr, size)
{
    if(size<=1)
      return;
    mergeSort(arr, size/2);
    mergeSort(arr+size/2, size -(size/2));
    int* ret = merge(arr, arr+size/2, size/2, size - size/2);
    for(int i=0; i<size; i++)
      arr[i] = ret[i];
}

Done!!

• Let the PC do the even odd, you do just the things you know.
• Memory: O(n).
• Time: theta n*log~2~n
• Possible bugs:

1. Code the merge function properly. Return the address of the aux space.
2. We need to all ms on the halves, and half sizes. Don’t worry about the even odd.
3. Copy the merged things into the actual input places, using for loop. Free the aux;

Merge Sort