Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Merge Sort Algorithm

    • 0
    • 4
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 516
    Comment on it

    Merge sort is a sorting algorithm that uses "Divide and Conquer" method to sort the array.It divides the array into two halves and then recursively sort the two sub-array and then merge the two sorted sub-arrays into sequence.

    Time complexity of Merge Sort is O(nLogn) in all 3 cases (worst, average and best).


    Algorithm of merge sort ::


    MergeSort(array[], left, right)
    If right > 1

    1. Find the middle point to divide the array into two halves:
      middle = (left+right)/2

    2. Call mergeSort for first half:
      MergeSort(array, left, middle)

    3. Call mergeSort for second half:
      MergeSort(array, middle+1, right)

    4. Merge the two halves sorted in step 2 and 3:
      MergeArray(array, left, middle, right)

    For eg.:

                     5    4     2     6     1     3    2    6           unsorted array
                             /\                         /\              divide
                 | 5  4      2  6  |             | 1   3     2    6 |
                    /\         /\                   /\         /\       divide
                | 5  4 |    | 2   6 |             | 1  3 |  |  2    6 |
                    /\          /\                     /\          /\   divide
               | 5 | | 4 |  | 2 | | 6 |          | 1 | |  3 |  | 2 | |  6 |
                    \/          \/                    \/           \/   merge
                 | 4  5 |    | 2  6 |             | 1   3 |    | 2   6 |
                          \/                                \/          merge
                    | 2   4   5  6 |                |  1   2   3   6 |
                                           \/                           merge
                        | 1    2     2     3    4     5    6    6 |     sorted array
    

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: