CSE 116 Lecture Notes - Lecture 5: Merge Sort, Stochastic Process, The Algorithm
Document Summary
Cse 116 intro to computer science ii. The problem to be solved is the building of a merge- sort program using: the sorting process is very time-efficient, the algorithm is straightforward; all the work is done in the merge portion of the program. The array to be sorted is split in half, each half is sorted and the sorted halves are merged. The function that divides the array in half calls itself twice, passing each half of the array in turn. After the second half has been returned, sorted, the two halves are merged and the result is the entire array, sorted. This subdividing continues until the elements to be sorted number 1 or 2. They are then put into order and the process of returning and merging begins. Pass right 2 elements to sorter to sorter. Since the elements are random and it checks itself for correct sorting, no further testing is necessary.