Forums Programming Assignment Help What is Merge Sort?

This topic contains 1 reply, has 1 voice, and was last updated by  aastha 3 years, 8 months ago.

Viewing 2 posts - 1 through 2 (of 2 total)
  • Author
    Posts
  • #15707

    aastha
    Member

    What is Merge Sort?

    #15708

    aastha
    Member

    Merge sort is used to sort element of an array. In merge sort the existing array is divided into two equal halves which are sorted (result of sub-problem) separately and merged again to give the array in sorted form.
    Merge sort uses divide and conquer approach.
    Steps Involved: –
    Array- A, Size- n,
    1. Divide the A in two halves A1, A2 containing
    • n/2 elements each if n is even.
    • First (n-1)/2 and last (n+1)/2 elements respectively.
    2. Repeat Step 1 on A1 and A2 separately in Step 1 until size of A1=1 and size of A2= 1.
    3. Merging A1 and A2 into A.
    initialize i,j,k= 0.
    while(i< sizeof(A1) && j<sizeof(A2))
    If(A1[i]<= A2[j])
    A[k]= A1[i]
    i++, k++
    else
    A[k]= A2[j]
    j++, k++
    while(i< sizeof(A1)) //if(sizeof(A1)> sizeof(A2)
    A[k]= A1[i]
    k++, i++
    while(j<sizeof(A2)) //if(sizeof(A2)> sizeof(A1)
    A[k]= A1[j]
    k++, j++

    Time Complexity
    Size decreases by a factor of 2 for each sub problem and there are two recursive calls made at each step therefore,
    T(n)= 2T(n/2) + cn
    Therefore time complexity of merge sort is of the order O(n log(n)).

Viewing 2 posts - 1 through 2 (of 2 total)

You must be logged in to reply to this topic.