mergesort

1MergeSort(arr[], l,  r)
2If r > l
3     1. Find the middle point to divide the array into two halves:  
4             middle m = l+ (r-l)/2
5     2. Call mergeSort for first half:   
6             Call mergeSort(arr, l, m)
7     3. Call mergeSort for second half:
8             Call mergeSort(arr, m+1, r)
9     4. Merge the two halves sorted in step 2 and 3:
10             Call merge(arr, l, m, r)

1//merge sort
2#include <iostream>
3
4using namespace std;
5void merge(int arr[],int start,int mid,int end)
6{
7    int n1=mid-start+1;
8    int n2=end-mid;
9    int l[n1],m[n2];
10    for(int i=0;i<n1;i++)
11    {
12        l[i]=arr[start+i];
13    }
14    for(int j=0;j<n2;j++)
15    {
16        m[j]=arr[mid+1+j];
17    }
18    int i=0;
19    int j=0;
20    int k=start;
21    while(i<n1&&j<n2)
22    {
23        if(l[i]<m[j])
24        {
25            arr[k]=l[i];
26            k++;
27            i++;
28        }
29        else
30        {
31            arr[k]=m[j];
32            k++;
33            j++;
34        }
35    }
36    while(i<n1)
37    {
38        arr[k]=l[i];
39        k++;
40        i++;
41    }
42    while(j<n2)
43    {
44        arr[k]=m[j];
45        k++;
46        j++;
47    }
48}
49void mergesort(int arr[],int start,int end)
50{
51    if(start<end)
52    {
53        int mid=(start+end)/2;
54        mergesort(arr,start,mid);
55        mergesort(arr,mid+1,end);
56        merge(arr,start,mid,end);
57    }
58}
59void display(int arr[],int n)
60{
61    for(int i=0;i<n;i++)
62    {
63        cout<<arr[i]<<" ";
64    }
65    cout<<endl;
66}
67
68int main()
69{
70    int n;
71    cout<<"enter the size of the array:"<<endl;
72    cin>>n;
73    cout<<"enter the elements of the array:"<<endl;
74    int arr[n];
75    for(int i=0;i<n;i++)
76    {
77        cin>>arr[i];
78    }
79    cout<<"array as it is:"<<endl;
80    display(arr,n);
81    cout<<"sorted array:"<<endl;
82    mergesort(arr,0,n-1);
83    display(arr,n);
84    return 0;
85}
86

1def merge_sort(arr):
2    if len(arr) > 1:
3        middle = len(arr) // 2
4        left = arr[:middle]
5        right = arr[middle:]
6
7        merge_sort(left)
8        merge_sort(right)
9
10        i = len(arr) - 1
11        while i >= 0:
12            if left and right:
13                if left[-1] >= right[-1]:
14                    arr[i] = left.pop()
15                else:
16                    arr[i] = right.pop()
17            else:
18                arr[i] = left.pop() if left else right.pop()
19            i -= 1
20    return arr

1class Sort 
2{
3    void merge(int arr[], int left, int middle, int right)
4    {
5        int low = middle - left + 1;                    //size of the left subarray
6        int high = right - middle;                      //size of the right subarray
7 
8        int L[] = new int[low];                             //create the left and right subarray
9        int R[] = new int[high];
10
11        int i = 0, j = 0;
12 
13        for (i = 0; i < low; i++)                               //copy elements into left subarray
14        {
15            L[i] = arr[left + i];
16        }
17        for (j = 0; j < high; j++)                              //copy elements into right subarray
18        {
19            R[j] = arr[middle + 1 + j];
20        }
21        
22 
23        int k = left;                                           //get starting index for sort
24        i = 0;                                             //reset loop variables before performing merge
25        j = 0;
26
27        while (i < low && j < high)                     //merge the left and right subarrays
28        {
29            if (L[i] <= R[j]) 
30            {
31                arr[k] = L[i];
32                i++;
33            }
34            else 
35            {
36                arr[k] = R[j];
37                j++;
38            }
39            k++;
40        }
41 
42        while (i < low)                             //merge the remaining elements from the left subarray
43        {
44            arr[k] = L[i];
45            i++;
46            k++;
47        }
48 
49        while (j < high)                           //merge the remaining elements from right subarray
50        {
51            arr[k] = R[j];
52            j++;
53            k++;
54        }
55    }
56 
57
58    void mergeSort(int arr[], int left, int right)       //helper function that creates the sub cases for sorting
59    {
60        int middle;
61        if (left < right) {                             //sort only if the left index is lesser than the right index (meaning that sorting is done)
62            middle = (left + right) / 2;
63 
64            mergeSort(arr, left, middle);                    //left subarray
65            mergeSort(arr, middle + 1, right);               //right subarray
66 
67            merge(arr, left, middle, right);                //merge the two subarrays
68        }
69    }
70 
71    void display(int arr[])                 //display the array
72    {  
73        for (int i=0; i<arr.length; ++i) 
74        {
75            System.out.print(arr[i]+" ");
76        } 
77    } 
78
79    public static void main(String args[])
80    {
81        int arr[] = { 9, 3, 1, 5, 13, 12 };
82        Sort ob = new Sort();
83        ob.mergeSort(arr, 0, arr.length - 1);
84        ob.display(arr);
85    }
86}
87

1void merge(int arr[], int l, int m, int r)
2    {
3         int n=r-l+1,temp[n];
4         int i=l,j=m+1,k=0;
5         while(i<=m and j<= r)
6         {
7             if(arr[i]< arr[j]){
8                temp[k++] = arr[i++];
9             else
10                temp[k++] = arr[j++];
11         }
12         while(i<=m)
13            temp[k++] = arr[i++];
14         while(j<=r)
15            temp[k++] = arr[j++];
16         int ind= 0;
17         for(int i=l;i<=m;i++)
18             arr[i] = temp[ind++];
19         for(int j=m+1;j<=r;j++)
20            arr[j] = temp[ind++];
21    }
22    
23    void mergeSort(int arr[], int l, int r)
24    {
25       if(l<r)
26       {
27           int mid = (r+l)/2;
28           mergeSort(arr,l,mid);
29           mergeSort(arr,mid+1,r);
30           merge(arr,l,mid,r);
31       }
32    }

1import java.util.ArrayList;
2import java.util.List;
3import java.util.Scanner;
4
5public class Main {
6
7    public static void main(String[] args) {
8        int size = 5 ;
9      double[] arrayList = new double[size];
10      for(int i = 0 ; i < arrayList.length ; ++i){
11          arrayList[i] = (Math.random()*1000);
12      }
13
14        mergeSort(arrayList,0,arrayList.length-1);
15        print(arrayList);
16
17    }
18    public static void print(double []  arrayList){
19        for(int i = 0 ; i < arrayList.length; ++i){
20            System.out.println(arrayList[i]);
21        }
22    }
23    public  static void mergeSort(double [] arr , int l , int r){
24        if(l<r){
25            int m = l+(r-l)/2;
26
27            mergeSort(arr,l,m);
28            mergeSort(arr,m+1,r);
29
30            merge(arr,l , m , r);
31        }
32
33    }
34
35    public  static void merge(double[] unsorted, int l , int m , int r){
36        int i ,j ,k;
37        int arr1 = m - l +1;
38        int arr2 = r - m ;
39        double [] left = new double[arr1];
40        double [] right = new double[arr2];
41        for(int f = 0 ; f < arr1 ; ++f){
42            left[f] = unsorted[l+f];
43        }
44        for (int s = 0 ; s < arr2 ; ++s){
45           right[s] = unsorted[m+1+s];
46        }
47
48        i = j = 0;
49        k = l ;
50
51        while(i < arr1 && j < arr2){
52            if(left[i] <= right[j]){
53                unsorted[k] = left[i];
54                ++i;
55            }
56            else {
57                unsorted[k]= right[j];
58                ++j;
59            }
60            ++k;
61        }
62
63        while(i<arr1){
64            unsorted[k] = left[i];
65            ++i;++k;
66        }
67        while(j<arr2){
68            unsorted[k] = right[j];
69            ++j;++k;
70        }
71
72
73    }
74}
75
76
77