Mergesort
Mergesort: basic idea
- split the array into two equal-sized paritions
- (recursively) sort each of the partitions
- merge the two partitions into a new sorted array
- copy back to original array
Merging: basic idea
- copy elements from the inputs one at a time
- give preference to the smaller of the two
- when one exhausted, copy the rest of the other
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}