% Merge Sort % Brian E. Lavender % April 15, 2016 # Merge Sort Concept Sorts an array of values * **Divide and Conquer**: * **Recursive Routine** * **Complexity**. O(Nlog~2~N) * **Disadvantage**: auxiliary array # Merge two sorted halves Example Two sorted arrays of size *k/2*. **Merge** them to destination of size *k*. min(4,8)? Left Half (size 4) | 0 | 1 | 2 | 3 | | ------- | ---- | ---- | ---- | | **4** | 15 | 16 | 50 | Right Half (size 4) | 0 | 1 | 2 | 3 | | ------- | ---- | ---- | ---- | | **8** | 23 | 42 | 108 | Destination (size 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | ---- | ---- | ---- | --- | --- | --- | --- | | _ | _ | _ | _ | _ | _ | _ | _ | # Merge Half Arrays To Destination (Step 1) Move *4* from left_half to destination min(15,8)? Left Half (size 4) | 0 | 1 | 2 | 3 | | --- | ------ | ---- | ---- | | * | **15** | 16 | 50 | Right Half (size 4) | 0 | 1 | 2 | 3 | | ------- | ---- | ---- | ---- | | **8** | 23 | 42 | 108 | Destination (size 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | ---- | ---- | ---- | --- | --- | --- | --- | | 4 | | | | | | | |