Merging is the process of combining two or more sorted files into a third sorted file. Merge sort is based on the divide and conquer paradigm. It can be explained as …. Let A[p…..r] is given array with indices p = 1 to r = n. Then steps can be
Image Source: http://en.wikipedia.org/wiki/Merge_sort
- Divide Step: If a given array A has zero or one element, then simply return; it is already sorted. Otherwise split A[p…..r] into two subarrays as A[p….q] and A[q+1…..r] each containing about the half of the elements.
- Conquer Step: Conquer by recursively sorted the two sub-arrays A[p….q] and A[q+1….r]
- Combine Step: Combine the elements back in A[p…..r] by merging the two sorted sub-arrays into the sorted sequence. Note that: the recursion bottoms out when the sub-array has just one element. So that it is trivially sorted.
تعليقات: 0
إرسال تعليق