Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- void sort(int *a, int l);
- void merge(int *L, int *R, int *a, int l);
- int main(void) {
- //Initial size of the array
- int a[100];
- //n stores size of the array and i is used in for loop
- int i,n;
- //Input the size of the array from the user must be less than initial size of the array
- printf("Enter the sie of array : ");
- scanf("%d", &n);
- //Taking input from the user and storing it in the array
- for(i=0; i<n;i++){
- scanf("%d", &a[i]);
- }
- //Calling function sort passing the array and size
- sort(a,n);
- //Printing the sorted array
- for(i=0; i<n; i++){
- printf("%d ",a[i]);
- }
- return 0;
- }
- //Sort method with pointer to the base address of the array and length
- //In C arrays are always passed by reference
- void sort(int *a, int l){
- //mid = middle index of the array passed
- int mid;
- //variable for for loop
- int i;
- //Pointers for Left and Right Halves
- int *L,*R;
- //If the size of array is 1 the array is sorted, so return
- if(l>1){
- mid = l/2;
- //Slicing the array into two halves l-Left and R-Right
- L = (int*)malloc(sizeof(int)*mid);
- R = (int*)malloc(sizeof(int)*(l-mid));
- //Copying the values in the left half
- for(i=0; i<mid; i++){
- L[i] = a[i];
- }
- //Copying the values in the right half
- for(i=mid; i<l; i++){
- R[i-mid] = a[i];
- }
- //Recursively calling sort function for left and right half
- sort(L,mid);
- sort(R,l-mid);
- //After the left and right half is sorted merge them
- //Passing the Left array, Right array and the original array and the length
- merge(L,R,a,l);
- }
- //Exit condition
- else{
- return;
- }
- }
- //Merge function
- void merge(int *L, int *R, int *a, int l){
- //i = Starting index for Left array
- int i=0;
- //mL = End index for Left array
- int mL = l/2;
- //j = Starting index for Right array
- int j=0;
- //mR = End index for Right array
- int mR = l-mL;
- //k = Starting index for the original array
- int k=0;
- //Compare the elements in Left and Right array until one is exhausted and put them in the original array
- while(i < mL && j < mR){
- if(L[i] < R[j]){
- a[k] = L[i];
- i++;
- }
- else{
- a[k] = R[j];
- j++;
- }
- k++;
- }
- //Copy the remaining elements from Left array to the original array
- while(i<mL){
- a[k] = L[i];
- i++;
- k++;
- }
- //Copy the remaining elements from the Right array to the original array
- while(j<mR){
- a[k] = R[j];
- j++;
- k++;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement