merge sort

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

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    }

1// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
2// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
3
4function merge(list, start, midpoint, end) {
5    const left = list.slice(start, midpoint);
6    const right = list.slice(midpoint, end);
7    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
8        if (topLeft >= left.length) {
9            list[i] = right[topRight++];
10        } else if (topRight >= right.length) {
11            list[i] = left[topLeft++];
12        } else if (left[topLeft] < right[topRight]) {
13            list[i] = left[topLeft++];
14        } else {
15            list[i] = right[topRight++];
16        }
17    }
18}
19
20function mergesort(list, start = 0, end = undefined) {
21    if (end === undefined) {
22        end = list.length;
23    }
24    if (end - start > 1) {
25        const midpoint = ((end + start) / 2) >> 0;
26        mergesort(list, start, midpoint);
27        mergesort(list, midpoint, end);
28        merge(list, start, midpoint, end);
29    }
30    return list;
31}
32
33mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

1# Python3 recursive merge sort algorithm -> O(n*log(n))
2def merge_sort(A):
3    def merge(l, r):
4        i = j = 0
5        n = []  # merging container
6        while i < len(l) or j < len(r):
7
8            # if no more elements to the right,
9            # add remaining left elements
10            if i == len(l):
11                n.extend(r[j:])
12                break
13
14            # if no more elements to the left,
15            # add remaining right elements
16            if j == len(r):
17                n.extend(l[i:])
18                break
19
20            # if elements left on both sides,
21            # add smaller element
22            a, b = l[i], r[j]
23            if a < b:
24                n.append(a)
25                i += 1
26            else:
27                n.append(b)
28                j += 1
29
30        return n
31
32    # divide list down to single-elements
33    s = len(A)
34    if s > 1:
35        s //= 2
36        l = merge_sort(A[:s])  # split left
37        r = merge_sort(A[s:])  # split right
38        return merge(l, r)  # merge sides in order
39    else:
40        return A

1Step 1 − if it is only one element in the list it is already sorted, return.
2Step 2 − divide the list recursively into two halves until it can no more be divided.
3Step 3 − merge the smaller lists into new list in sorted order.
4

1Given array is 
212 11 13 5 6 7 
3Sorted array is 
45 6 7 11 12 13