“Merge two lists so that, the resulting list should be sorted is the main concept behind Merge sort. As we have seen in any sorting algorithm, something is assumed initially as a sorted number. In merge sort, if any two random numbers are merged, they are sorted.”
See first:
http://analgorithmaday.blogspot.com/2011/01/merge-algorithm.html
Metaphor
Merging lists has the same metaphor as explained in the above link. But sorting by merging in real world happens when you have 2 things sorted already and want to merge both. Its used in comparatively large data set sorting since, we assume 2 lists are sorted to start with the algorithm. The division of the large data set can happen very easily in merge sort and it requires constant space, and very less random access as we do direct copy into the master list. But note that merge sort operates over RAM based arrays.
Concept
Split the master list into 2. Take the least of the elements in the 2 lists and place it in the master list. But note that, the final solution of getting master list can happen only when the master list is split along the index which divides it into 2 sorted list. This cannot be found on a randomly sorted list. Then how to manage it.
This is how, Consider, A = { 5, 3, 2, 4}
split, into A1 = {5,3}, A2 = {2,4}
further split, A3 = {5}, A4={3}, A5={2}, A6={4}
Note here that, A3, A4, A5, A6 are all sorted. Now, we can merge A3, A4 and A5, A6 which gives 2 sorted list,
Like, A1 ={3,5}, A2={2,4}. We can destroy temporary lists A3, A4, A5, A6 and also process merge within these lists in different systems even!!
Now, A1, A2 are already sorted list. Sort both to get A={2,3,4,5} which makes the master list to get sorted.
A(0, 3)
/ \
/ \
/ \
A1(0, 1) A2(2, 3)
/ \ / \
/ \ / \
A3(0, 0) A4(1, 1) A5(2, 2) A6(3, 3)
Note that when running in a recursion, A3, A4, A5, A6 will all return without a merge and only A1(0,1) and A2(2,3) goes as input to the merge algorithm. Final merge is done with A(0,3) to get the sorted list.
Master getting split into various child lists to reach a base condition from where combine happens is known as divide-conquer-combine methodology. All the algorithms which comes under this category is easy to implement using 2-function recursion (like Fibonacci) as we divide the problem into 2. There is a problem called Towers of Hanoi where we divide the problem into 3. 
We will see that in future.
Code
In the below code, merge method is again shown. There are some bug fixes done on this merge version. These are the fixes:
- There is no need for a error condition check where mid is zero or end is zero. mid can be zero in cases when start is zero. But end cannot be zero. For that, we can have a check!
- free is a must!! otherwise, you leak memory. The code given in merge algorithm has a free but it creates heap corruption. Heap corruption happens when you allocate less and occupy more on the memory. So, free will crash in the merge code. So, we need to put extra bit in malloc. And also best practise is to multiply it with sizeof(int)
1: 2: void merge(int *arr, int start, int mid, int end)
3: {4: // arr = List D = split into List A and List B
5: int n1, n2;
6: 7: n1 = mid - start + 1; // List A[0..n1-1]
8: n2 = end - mid; // List B[0..n2-1]
9: 10: int *la, *lb;
11: int i,j,k;
12: la = (int*) malloc(sizeof(int)*(n1+1));
13: lb = (int*) malloc(sizeof(int)*(n2+1));
14: 15: for(i=0; i<n1; i++)
16: {17: if(start == 0)
18: la[i] = arr[i];19: else
20: la[i] = arr[start+i]; 21: } 22: 23: for(j=0; j<n2; j++)
24: lb[j] = arr[mid+j+1]; 25: 26: la[n1] = INT_MAX; 27: lb[n2] = INT_MAX; 28: 29: i = 0; j =0;30: for(k = start; k<end+1; k++)
31: {32: if(la[i] < lb[j])
33: { 34: arr[k] = la[i]; 35: i = i + 1; 36: }37: else
38: { 39: arr[k] = lb[j]; 40: j = j + 1; 41: } 42: } 43: free(la); 44: free(lb); 45: } 46: 47: void merge_sort_recur(int* arr, int start, int end)
48: { 49: 50: if(start < end)
51: {52: int mid = (int) floor(((float)start+(float)end)/2);
53: merge_sort_recur(arr, start, mid); 54: merge_sort_recur(arr, mid+1, end); 55: merge(arr, start, mid, end); 56: } 57: } 58: 59: void main()
60: {61: int A[] = {5,2,4,7,1,3,2,6};
62: merge_sort_recur(A, 0, 7); 63: }Important issues got while writing the above code:
- Array index is very important!!. I initially give start = 0 and end = 8, which creates chaos. If you use zero index in the array, please give length-1 as end always
- The division of the array length, start+end/2 can lead to decimal points. By default, some machines ceil it and some floor it.
- ceil = Make the number to the next number in the number line. That is, 2.3 = 3 and 3.8 = 4
- floor = Keep only the number before the decimal point. That is, 2.3 = 2 and 3.8 = 3.
- Still the above code is not idiot-proof. Try different inputs and if you get any interesting problems, please comment.
- Note that, start<end is the important condition which breaks the recursion. When start = end or start > end.
- First expansion of start –> mid will be done and then we will be at a basic place where mid+1 and end is also equal. and then merge happens. and then again, mid+1, end split starts.
- split at left until end, split at the right until end, reach the center and merge left+right
Important points
- Merge sort follows the pattern of a data structure named tree. Merge sort starts at left, expands the right, and merges left and right. This is also known as post order traversal on a tree data structure.
- Merge sort is really an important concept and involves many internal hidden concepts to be understood well.
- Merge sort splits the array into a tree all over the function call stack and returns a sorted array finally. But internally the operations are done by converting the array into a tree.
- This is a 2 function recursion as it has 2 variants. The left and the right list. Whenever you have 2 lists processed recursively, you internally get a binary tree on the stack.
- If the recursion is single function one, it goes till the full depth at one side. But if it is two function, it goes full depth at either side first.
- There is something named tree traversal types hidden inside this.
- Merge sort using linked list, internally has a logic like converting the linked list to a tree. Moreover, such a method itself is an algorithm
- Merge sort effectively does divide-conquer-combine with the help of binary tree representation. This is not the only way but the most common way.
- This is the first sorting algorithm we saw, which has O(nlogn) performance and max O( n) space complexity.
Reference:
http://www.cprogramming.com/tutorial/computersciencetheory/mergesort.html
No comments:
Post a Comment