merge sort

//merge sort
#include <iostream>

using namespace std;
void merge(int arr[],int start,int mid,int end)
{
    int n1=mid-start+1;
    int n2=end-mid;
    int l[n1],m[n2];
    for(int i=0;i<n1;i++)
    {
        l[i]=arr[start+i];
    }
    for(int j=0;j<n2;j++)
    {
        m[j]=arr[mid+1+j];
    }
    int i=0;
    int j=0;
    int k=start;
    while(i<n1&&j<n2)
    {
        if(l[i]<m[j])
        {
            arr[k]=l[i];
            k++;
            i++;
        }
        else
        {
            arr[k]=m[j];
            k++;
            j++;
        }
    }
    while(i<n1)
    {
        arr[k]=l[i];
        k++;
        i++;
    }
    while(j<n2)
    {
        arr[k]=m[j];
        k++;
        j++;
    }
}
void mergesort(int arr[],int start,int end)
{
    if(start<end)
    {
        int mid=(start+end)/2;
        mergesort(arr,start,mid);
        mergesort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
}
void display(int arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    int n;
    cout<<"enter the size of the array:"<<endl;
    cin>>n;
    cout<<"enter the elements of the array:"<<endl;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    cout<<"array as it is:"<<endl;
    display(arr,n);
    cout<<"sorted array:"<<endl;
    mergesort(arr,0,n-1);
    display(arr,n);
    return 0;
}

4
3
Ty H. 110 points

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

4 (3 Votes)
0
4.25
4

                                    class Sort 
{
    void merge(int arr[], int left, int middle, int right)
    {
        int low = middle - left + 1;                    //size of the left subarray
        int high = right - middle;                      //size of the right subarray
 
        int L[] = new int[low];                             //create the left and right subarray
        int R[] = new int[high];

        int i = 0, j = 0;
 
        for (i = 0; i &lt; low; i++)                               //copy elements into left subarray
        {
            L[i] = arr[left + i];
        }
        for (j = 0; j &lt; high; j++)                              //copy elements into right subarray
        {
            R[j] = arr[middle + 1 + j];
        }
        
 
        int k = left;                                           //get starting index for sort
        i = 0;                                             //reset loop variables before performing merge
        j = 0;

        while (i &lt; low &amp;&amp; j &lt; high)                     //merge the left and right subarrays
        {
            if (L[i] &lt;= R[j]) 
            {
                arr[k] = L[i];
                i++;
            }
            else 
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        while (i &lt; low)                             //merge the remaining elements from the left subarray
        {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        while (j &lt; high)                           //merge the remaining elements from right subarray
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 

    void mergeSort(int arr[], int left, int right)       //helper function that creates the sub cases for sorting
    {
        int middle;
        if (left &lt; right) {                             //sort only if the left index is lesser than the right index (meaning that sorting is done)
            middle = (left + right) / 2;
 
            mergeSort(arr, left, middle);                    //left subarray
            mergeSort(arr, middle + 1, right);               //right subarray
 
            merge(arr, left, middle, right);                //merge the two subarrays
        }
    }
 
    void display(int arr[])                 //display the array
    {  
        for (int i=0; i&lt;arr.length; ++i) 
        {
            System.out.print(arr[i]+&quot; &quot;);
        } 
    } 

    public static void main(String args[])
    {
        int arr[] = { 9, 3, 1, 5, 13, 12 };
        Sort ob = new Sort();
        ob.mergeSort(arr, 0, arr.length - 1);
        ob.display(arr);
    }
}

4.25 (4 Votes)
0
0
0
MikeJ-UK 85 points

                                    // @see https://www.youtube.com/watch?v=es2T6KY45cA&amp;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 &lt; end; i += 1) {
        if (topLeft &gt;= left.length) {
            list[i] = right[topRight++];
        } else if (topRight &gt;= right.length) {
            list[i] = left[topLeft++];
        } else if (left[topLeft] &lt; 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 &gt; 1) {
        const midpoint = ((end + start) / 2) &gt;&gt; 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]);

0
0
4
6
Kristi 100 points

                                    void merge(int arr[], int l, int m, int r)
    {
         int n=r-l+1,temp[n];
         int i=l,j=m+1,k=0;
         while(i&lt;=m and j&lt;= r)
         {
             if(arr[i]&lt; arr[j]){
                temp[k++] = arr[i++];
             else
                temp[k++] = arr[j++];
         }
         while(i&lt;=m)
            temp[k++] = arr[i++];
         while(j&lt;=r)
            temp[k++] = arr[j++];
         int ind= 0;
         for(int i=l;i&lt;=m;i++)
             arr[i] = temp[ind++];
         for(int j=m+1;j&lt;=r;j++)
            arr[j] = temp[ind++];
    }
    
    void mergeSort(int arr[], int l, int r)
    {
       if(l&lt;r)
       {
           int mid = (r+l)/2;
           mergeSort(arr,l,mid);
           mergeSort(arr,mid+1,r);
           merge(arr,l,mid,r);
       }
    }

4 (6 Votes)
0
0
8
Savoie 95 points

                                    Given array is 
12 11 13 5 6 7 
Sorted array is 
5 6 7 11 12 13

0
0
4.4
5

                                    # Python3 recursive merge sort algorithm -&gt; O(n*log(n))
def merge_sort(A):
    def merge(l, r):
        i = j = 0
        n = []  # merging container
        while i &lt; len(l) or j &lt; len(r):

            # if no more elements to the right,
            # add remaining left elements
            if i == len(l):
                n.extend(r[j:])
                break

            # if no more elements to the left,
            # add remaining right elements
            if j == len(r):
                n.extend(l[i:])
                break

            # if elements left on both sides,
            # add smaller element
            a, b = l[i], r[j]
            if a &lt; b:
                n.append(a)
                i += 1
            else:
                n.append(b)
                j += 1

        return n

    # divide list down to single-elements
    s = len(A)
    if s &gt; 1:
        s //= 2
        l = merge_sort(A[:s])  # split left
        r = merge_sort(A[s:])  # split right
        return merge(l, r)  # merge sides in order
    else:
        return A

4.4 (5 Votes)
0
3.67
6
Volgograd 80 points

                                    MergeSort(arr[], l,  r)
If r &gt; l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (r-l)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

3.67 (6 Votes)
0
Are there any code examples left?
Create a Free Account
Unlock the power of data and AI by diving into Python, ChatGPT, SQL, Power BI, and beyond.
Sign up
Develop soft skills on BrainApps
Complete the IQ Test
Relative searches
merge sort working How does merge sort work? sort mergesort merge sort u merge sort who created merge sort merge sort algorithm def def merge sort merge sort meaning merge sortsort define merge sort Merge sort works using working of merge sort mergesort' implement merge sort sort merge Merge Sort is in place sort. merge sort priciple\ mergesort in how merge sort work merge sort work merge sort function merge sort concept merge sort comple when is merge sort when is merge sort used merge sort algorithme A Merge Sort. merge Sort is in place merge sort merge merge sorty merge sort merging how does a merge sort work sort using merge sort merge sort worst merge sort hs merge sortz where we use merge sort merge sort algorithm explained algorithm merge sort use of merge sort merge sort tutorial how to perform a merge sort HOw merge sort works? how to merge sort merge sort nedir how to sort in merge sort what is merge sort algorithm how merge sort works in merge sort, you create how merge sort is sorted Merge Sort algorithm. how to indicate order in merge sort merge sort in place merge sort. merge sort for what is a merge sort merge sort baeldung merge sort wiki how to implement merge sort merge sort explanation merge sort algorithm in place merge sorte definition of merge sort merge sort\ how does merge sort work merge sort demo what is merge sort used for merge and sort explain merge sort merge sort explained merge sort implement merge sort example merge sort ascending order merge sort \ merge sort a what is merge sort? merge sort com 9. Running merge sort on an array of size n which is already sorted is * mergesort \ merge sort complexity analysis merge sort sort complexity merge sort complexity selection insertion merge sort c++ merge sprt merge sort function c Let P be a mergesort program to sort numbers in ascendinng order on a unknown data structure which take O(n^2) time to find the mid element, rest property is unknown. Then recurrence relation for the same is ? big o notation merge sort merger sort c mergesort complexity merge and sort algorithm merge sort solve merge sort big o For the merge sort algorithm discussed in class, if the following change is made, the worst-case runtime would be average complexity of merge sort application of mergesort where gfg mergesort python merge sort i c++ merge sort recursive. c++ merge sort. marge sort in c merge sort algorithm merge sort implementation in c average tc of merge sort merge sort in matrix mergesort wiki merge-sort algorithm merge method for merge sort merge sort in c++ program c++ code for merge sort Mergesort complexity in already ascending order Implement following Merge sort algorithm using recursion print passes of merging algorithm. mergesort implementation c++ full implementation merge sort c++ c++ merge sort code merge sort recursive java merge sort time and space complexity space complexity of merge sort merge sort pseudocode geeks for geeks merge sort recursive C merge sort void* mergesort c merge sort theory implementation of merge sort algorithm in c++ A c code for merge sort Use tabbing with binary search in the merging process. merge sort in cpp code merge sort example with steps merge sort java recursion Determine the appropriate sorting algorithm corresponding to the below function: Function (m,n) {If(m&lt;n) {Mid=(m+n)/2; Sort(m,middle); Sort(middle+1,n); Sort(m,middle,n);}} * merge sort expressed mathematically mergesort code merge sort recursive c++ code merge sort code in c++ merge sort in cpp code for merge sort in c java merge sort simple function mergeSort(nums) { // Write merge sort code here. merge sort python complexity code for merge sort erge sort code merge sort cpp merge sort c++ program merge sort algorithm example merge sort python c++ merge sort merge sort and sort in c++ merge sort function in c++ mergesort function in c++ merge sorted array sorting string merge sort merge sort java merge sort in java MERGE sort TO SORT ARRAY merging sorting mergesort in c merged sort merge soring c++ merge sorting merge sorr merge sort source code how does the mergesort work what is merge sort merge sort more efficent way merge sort using auxiliary merge sort c++ geeksforgeeks merge sort recursive merge sort cpp merge sort definition merge sort array algo mergesort implementation java merge sort code merge sort algorithm geekforgeeks? merge sort algorithm? mergesort cpp code merge sort psuedocode merge sort c merge sort algo merge sort program in c++ merge sort in c merge sort algorithm merge sort code in c merge sort in c++ mergesort merge sort ascending c++ merge sort
Made with love
This website uses cookies to make IQCode work for you. By using this site, you agree to our cookie policy

Welcome Back!

Sign up to unlock all of IQCode features:
  • Test your skills and track progress
  • Engage in comprehensive interactive courses
  • Commit to daily skill-enhancing challenges
  • Solve practical, real-world issues
  • Share your insights and learnings
Create an account
Sign in
Recover lost password
Or log in with

Create a Free Account

Sign up to unlock all of IQCode features:
  • Test your skills and track progress
  • Engage in comprehensive interactive courses
  • Commit to daily skill-enhancing challenges
  • Solve practical, real-world issues
  • Share your insights and learnings
Create an account
Sign up
Or sign up with
By signing up, you agree to the Terms and Conditions and Privacy Policy. You also agree to receive product-related marketing emails from IQCode, which you can unsubscribe from at any time.
Creating a new code example
Code snippet title
Source