DEV Community

Cover image for Merge sort
Sourav das
Sourav das

Posted on

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

Discussion (0)