mergesort implementation c++

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en // @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html function merge(list, start, midpoint, end) { const left = list.slice(start, midpoint); const right = list.slice(midpoint, end); for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) { if (topLeft >= left.length) { list[i] = right[topRight++]; } else if (topRight >= right.length) { list[i] = left[topLeft++]; } else if (left[topLeft] < right[topRight]) { list[i] = left[topLeft++]; } else { list[i] = right[topRight++]; } } } function mergesort(list, start = 0, end = undefined) { if (end === undefined) { end = list.length; } if (end - start > 1) { const midpoint = ((end + start) / 2) >> 0; mergesort(list, start, midpoint); mergesort(list, midpoint, end); merge(list, start, midpoint, end); } return list; } mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

merge sort algorithm

/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array. 
*/

#include <stdio.h>

// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.

// merge sort function
void mergeSort(int a[], int p, int r)
{
    int q;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q+1, r);
        merge(a, p, q, r);
    }
}

// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
    int b[5];   //same size of a[]
    int i, j, k;
    k = 0;
    i = p;
    j = q + 1;
    while(i <= q && j <= r)
    {
        if(a[i] < a[j])
        {
            b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
        }
        else
        {
            b[k++] = a[j++];
        }
    }
  
    while(i <= q)
    {
        b[k++] = a[i++];
    }
  
    while(j <= r)
    {
        b[k++] = a[j++];
    }
  
    for(i=r; i >= p; i--)
    {
        a[i] = b[--k];  // copying back the sorted list to a[]
    } 
}

// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("n");
}
 
int main()
{
    int arr[] = {32, 45, 67, 2, 7};
    int len = sizeof(arr)/sizeof(arr[0]);
 
    printf("Given array: n");
    printArray(arr, len);
    
    // calling merge sort
    mergeSort(arr, 0, len - 1);
 
    printf("nSorted array: n");
    printArray(arr, len);
    return 0;
}

Posted by: Guest on August-08-2020

Source

Code answers related to "mergesort implementation c++"

Code answers related to "Python"

Browse Popular Code Answers by Language

Answers for "mergesort implementation c++"

Code answers related to "mergesort implementation c++"

Code answers related to "Python"

Python Answers by Framework

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us