How To Perform Merge Sort | Sorting Algorithm

In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm.It is a divide and conquer algorithm that was invented by John von Neumann in 1945.

  Algorithm 

     Conceptually, a merge sort works as follows:
  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list. 
The following diagram shows the complete merge sort process.
 


Source Code: 

Download the code: Merge.c

#include<stdio.h>
#include<stdlib.h>

void mergesort(int a[],int low,int high)
{
    int mid=(low+high)/2;
    if(low<high)
    {
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}
void merge(int a[],int low,int mid,int high)
{
    int x=high-low+1; 
    int *b;
    int i,j,k;
    i=low;
    j=mid+1;
    k=0;
    b=(int *)malloc(sizeof(int)*x);
    while(i<=mid && j<=high)
    {
        if(a[i]<=a[j])
        {
            b[k]=a[i];
       
            i++;
        }
        else
        {
            b[k]=a[j];
       
            j++;   
        }
    k++;       
    }
    if(i>mid)
    {
        while(j<=high)
        {
            b[k]=a[j];
            k++;
            j++;   
        }

    }
    else
    {
        while(i<=mid)
        {
            b[k]=a[i];
            k++;
            i++;   
        }   
    }
    k=0;
    for(i=low;i<=high;i++,k++)
    {
        a[i]=b[k];
    }
    free(b);
}
int main()
{
    int a[]={2,4,1,5,16,9,1},i;
    mergesort(a,0,6);
    for(i=0;i<7;i++)
    {
        printf("%d",a[i]);
    }
    return 0;
}

Output:

 

Comments

Post a Comment

Popular posts from this blog

How to create a Chess Game | Game Development in vb.net | Programming

Image
Chess,one of the most recognized board game in the world.You probably have played it once or seen it once in your lifetime.How cool it would be if we can create our own chess game. Here is the code,you can use to as reference for creating your own or you can just just clone it from Github and improve My version of Chess.  Download the code : Github :  VB_Chess (Visual Studio 2010) King.vb Public Class king     Public x_pos, y_pos As Integer     Public piece_val As Integer     Public flags(7, 7) As Boolean     Public check_the_king(7, 7) As Boolean     Public Sub New(ByVal x, ByVal y, ByVal p_val)   'color=+ve val if white color=-ve if black          x_pos = x         y_pos = y         piece_val = p_val         re_flags()     End Sub     Public Function ret_x() As Integer         Return x_pos     End Function  Public Function ret_y() As Integer         Return y_pos     End Function     Public Function ret_val() As Integer         Return piece
Read more

Write a program to print all permutations of a given string

Image
A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation. Below are the permutations of string ABC. ABC ACB BAC BCA CBA CAB. Source Code:  Download the code  : Permutation of string #include <iostream> #include <string.h> using namespace std; int count=0; void swap(char *x, char *y) {     char temp;     temp = *x;     *x = *y;     *y = temp; } void permute(char *a, int l, int r) {    int i;    if (l == r)    {     count++;     cout<<count<<": "<<a<<"\n";    }    else    {        for (i = l; i <= r; i++)        {           swap((a+l), (a+i));           permute(a, l+1, r);           swap((a+l), (a+i));        }    } } int main() {     char str[100];     int n;     cin>>str;     cout<<"\nPermutations of the given string :\n";     n = strlen(s
Read more