Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.74 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void sort(int *a, int l);
  5. void merge(int *L, int *R, int *a, int l);
  6.  
  7. int main(void) {
  8. //Initial size of the array
  9. int a[100];
  10.  
  11. //n stores size of the array and i is used in for loop
  12. int i,n;
  13.  
  14. //Input the size of the array from the user must be less than initial size of the array
  15. printf("Enter the sie of array : ");
  16. scanf("%d", &n);
  17.  
  18. //Taking input from the user and storing it in the array
  19. for(i=0; i<n;i++){
  20. scanf("%d", &a[i]);
  21. }
  22.  
  23. //Calling function sort passing the array and size
  24. sort(a,n);
  25.  
  26. //Printing the sorted array
  27. for(i=0; i<n; i++){
  28. printf("%d ",a[i]);
  29. }
  30.  
  31. return 0;
  32. }
  33.  
  34. //Sort method with pointer to the base address of the array and length
  35. //In C arrays are always passed by reference
  36. void sort(int *a, int l){
  37. //mid = middle index of the array passed
  38. int mid;
  39. //variable for for loop
  40. int i;
  41. //Pointers for Left and Right Halves
  42. int *L,*R;
  43.  
  44. //If the size of array is 1 the array is sorted, so return
  45. if(l>1){
  46. mid = l/2;
  47. //Slicing the array into two halves l-Left and R-Right
  48. L = (int*)malloc(sizeof(int)*mid);
  49. R = (int*)malloc(sizeof(int)*(l-mid));
  50.  
  51. //Copying the values in the left half
  52. for(i=0; i<mid; i++){
  53. L[i] = a[i];
  54. }
  55. //Copying the values in the right half
  56. for(i=mid; i<l; i++){
  57. R[i-mid] = a[i];
  58. }
  59.  
  60. //Recursively calling sort function for left and right half
  61. sort(L,mid);
  62. sort(R,l-mid);
  63.  
  64. //After the left and right half is sorted merge them
  65. //Passing the Left array, Right array and the original array and the length
  66. merge(L,R,a,l);
  67. }
  68. //Exit condition
  69. else{
  70. return;
  71. }
  72. }
  73.  
  74.  
  75. //Merge function
  76. void merge(int *L, int *R, int *a, int l){
  77. //i = Starting index for Left array
  78. int i=0;
  79. //mL = End index for Left array
  80. int mL = l/2;
  81. //j = Starting index for Right array
  82. int j=0;
  83. //mR = End index for Right array
  84. int mR = l-mL;
  85. //k = Starting index for the original array
  86. int k=0;
  87.  
  88. //Compare the elements in Left and Right array until one is exhausted and put them in the original array
  89. while(i < mL && j < mR){
  90. if(L[i] < R[j]){
  91. a[k] = L[i];
  92. i++;
  93. }
  94. else{
  95. a[k] = R[j];
  96. j++;
  97. }
  98. k++;
  99. }
  100.  
  101. //Copy the remaining elements from Left array to the original array
  102. while(i<mL){
  103. a[k] = L[i];
  104. i++;
  105. k++;
  106. }
  107.  
  108. //Copy the remaining elements from the Right array to the original array
  109. while(j<mR){
  110. a[k] = R[j];
  111. j++;
  112. k++;
  113. }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement