DEV Community

Cover image for Merge sort
Sourav das
Sourav das

Posted on

1 1

Merge sort

In cpp

#include <iostream>
using namespace std;
void ms(int *arr,int low,int mid,int high)
{
    int b[low+high];
    int i=low;
    int j=mid+1;
    int k=low;
    while(i<=mid && j<=high)
    {
        if (arr[i]<arr[j])
        {
            b[k]=arr[i];
            i++;
        }
        else
        {
            b[k]=arr[j];
            j++;
        }
        k++;
    }
    while(i<=mid)
    {   
        b[k]=arr[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        b[k]=arr[j];
        j++;
        k++;
    }
    int p=low;
    while(p<k)
    {
        arr[p]=b[p];
        p++;
    }
}
void divide(int *arr,int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        divide(arr,low,mid);
        divide(arr,mid+1,high);
        ms(arr,low,mid,high);
    }
}
int main()
{
    int arr[]={5,6,8,9,1};
    divide(arr,0,5);
    for (int i = 0; i < 5; ++i)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
Enter fullscreen mode Exit fullscreen mode

In python

def ms(n):
    if len(n)>1:
        mid=len(n)//2
        lefthalf=n[:mid]
        righthalf=n[mid:]
        ms(lefthalf)
        ms(righthalf)
        i=j=k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                n[k]=lefthalf[i]
                i+=1
                k+=1
            else:
                n[k]=righthalf[j]
                j+=1
                k+=1
        while i<len(lefthalf):
            n[k]=lefthalf[i]
            i+=1
            k+=1
        while j<len(righthalf):
            n[k]=righthalf[j]
            j+=1
            k+=1
    return n
a=[9,1,5,3,4,3]
print(ms(a))
Enter fullscreen mode Exit fullscreen mode

in ruby

def ms n
    if n.size>1
        mid=n.size/2
        left=n.slice(0,mid)
        right=n.slice(mid,100)
        ms left
        ms right
        i=j=k=0
        while i<left.size && j<right.size
            if left[i]<right[j]
                n[k]=left[i]
                i+=1
                k+=1
            else
                n[k]=right[j]
                j+=1
                k+=1
            end
        end
        while i<left.size
            n[k]=left[i]
            i+=1
            k+=1
        end
        while j<right.size
            n[k]=right[j]
            j+=1
            k+=1
        end
    end
    return n
end

n=[9,6,4,1,2]
print ms n
puts
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more