Merge Sort
The merge sort algorithm will be discussed in this article. Merge sort is a sorting method that uses the divide and conquers method. This essay will be highly useful and fascinating to students who may be asked about merge sort in their exams. Sorting algorithms are frequently asked in coding or technical interviews for software professionals. As a result, it is critical to debate the subject.
Merge sort is similar to the rapid sort algorithm in that it sorts the elements using a divide and conquer strategy. It's one of the most widely used and effective sorting algorithms. It splits the given list into two halves, then calls itself for each half and merges the two sorted parts. To perform the merging, we must define the merge() function.
The sub-lists are divided into halves repeatedly until the list can no longer be divided. Then we combine the two one-element lists into a two-element list while sorting them. The sorted two-element pairs are combined into four-element lists until the sorted list is obtained.
Let's look at my algorithm now.
Algorithm
- The provided array is arr, the first element is beg, and the last element is end in the following procedure.
- MERGE SORT is a function that sorts data (arr, beg, end)
-
- Set mid = (beg + end)/2 if start and end are the same.
- MERGE SORT(arr, beg, mid) MERGE SORT(arr, mid + 1, end) MERGE SORT(arr, mid + 1, end)
- end of if MERGE (arr, beg, mid, end)
-
- MERGE SORT END
<![CDATA[
1. The MERGE function is a crucial feature of the merge sort.
This function merges two sorted sub-arrays, A[beg...mid] and A[mid+1...end],
to create one sorted array A[beg...end]. A[], beg, mid, and end are the MERGE function's inputs.
2. The following is the MERGE function's implementation. -
3. void merge /* Merge the subarrays of a[]
*/ void merge /* Merge the subarrays of a[] */ void merge (int a[], int beg, int mid, int end)
4. int I j, k; int n1 = mid - begin + 1; int n2 = end - begin; int n3 = end - begin;
int n4 = end - begin; int n5 = end - begin; int n6 = end - begin; int n
5.
6. /temporary arrays int LeftArray[n1], RightArray[n2];
7. /* copy data to temp arrays */
8. http://localhost/datastructures/quick.html for (int i = 0; i < n1; i++)
9. LeftArray[i] = a[beg + i];
10. for (int j = 0; j < n2; j++)
11. RightArray[j] = a[mid + 1 + j];
12.
13. j = 0; /* initial index of second sub-array */ k = beg; /* initial index of merged sub-array */
I = 0, /* initial index of first sub-array */ j = 0; /* initial index of second sub-array *//
14.
15. while (i < n1 && j < n2)
16. {
17. if(LeftArray[i] <= RightArray[j])
18. {
19. a[k] = LeftArray[i];
20. i++;
21. }
22. else
23. {
24. a[k] = RightArray[j];
25. j++;
26. }
27. k++;
28. }
29. while (i<n1)
30. {
31. a[k] = LeftArray[i];
32. i++;
33. k++;
34. }
35.
36. while (j<n2)
37. {
38. a[k] = RightArray[j];
39. j++;
40. k++;
41. }
42. }
]]>
