Scribd Logo
Upload

Welcome to Scribd!

  • 763 views

    Merge Sort

    Uploaded by

    Arnex Fesariton
    Merge sort is a divide and conquer algorithm that works as follows: 1. Divide the list into equal halves until you have lists with single elements 2. Merge the single element lists back together in a sorted order by comparing elements from each list and writing the smaller value into the output list 3. Repeat merging the sorted lists until the entire input list is sorted It has advantages of being a stable sort and requiring only O(n log n) time. The key steps are dividing, sorting the sublists recursively, and merging the sorted sublists back together.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Merge Sort

    Uploaded by

    Arnex Fesariton
    763 views3 pages
    Merge sort is a divide and conquer algorithm that works as follows: 1. Divide the list into equal halves until you have lists with single elements 2. Merge the single element lists back together in a sorted order by comparing elements from each list and writing the smaller value into the output list 3. Repeat merging the sorted lists until the entire input list is sorted It has advantages of being a stable sort and requiring only O(n log n) time. The key steps are dividing, sorting the sublists recursively, and merging the sorted sublists back together.

    Original Title

    merge sort

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Merge sort is a divide and conquer algorithm that works as follows: 1. Divide the list into equal halves until you have lists with single elements 2. Merge the single element lists back together in a sorted order by comparing elements from each list and writing the smaller value into the output list 3. Repeat merging the sorted lists until the entire input list is sorted It has advantages of being a stable sort and requiring only O(n log n) time. The key steps are dividing, sorting the sublists recursively, and merging the sorted sublists back together.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    763 views3 pages

    Merge Sort

    Uploaded by

    Arnex Fesariton
    Merge sort is a divide and conquer algorithm that works as follows: 1. Divide the list into equal halves until you have lists with single elements 2. Merge the single element lists back together in a sorted order by comparing elements from each list and writing the smaller value into the output list 3. Repeat merging the sorted lists until the entire input list is sorted It has advantages of being a stable sort and requiring only O(n log n) time. The key steps are dividing, sorting the sublists recursively, and merging the sorted sublists back together.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 3

    Merge Sort

    Algorithm
    Conceptually, a merge sort works as follows
    Merge Sort – Divide & Conquer
    •Divide:
    Divide the n-element sequence to be sorted into two
    subsequences of n/2 elements each.
    •Conquer:
    Sort the two subsequences recursively (I.e. by using
    merge sort again on the subsequences).
    •Combine:
    Merge the two sorted subsequences to produce the
    sorted answer.
    • This procedure will bottom out when the list to be sorted is of length 1
    so we must take this into account in our algorithm design.

    Merge sort incorporates two main ideas to improve its runtime:


    1. A small list will take fewer steps to
    sort than a large list.
    2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists.
    For example, you only have to traverse each list once if they're already sorted.
    Advantages:

    Many useful algorithms are recursive


    • These algorithms employ a divide and conquer approach.
    • Think of merging two lists of sorted numbers.
    • All that is needed is to look at the top items and add the
    appropriate one each time
    • The merge sort algorithm closely follows the Divide and
    Conquer paradigm. It operates as follows,

    Merge Sort – Visual Example


    75 55 15 20 85 30 35 10 60 40 50 25 45 80 70 65
    • Divide list into 2 sublist, so at next level of recursion we have :
    75 55 15 20 85 30 35 10
    Sub-list 1
    60 40 50 25 45 80 70 65
    Sub-list 2
    • We keep splitting our sublists into smaller sublists until we can’t split any further
    • Eventually we will end up with distinct pairs of already sorted sublists which need to be
    merged together.
    75 55 15 20 85 30 35 10 60 40 50 25
    70 65

    75 55

    85 30
    35 10
    60 40
    50 25
    45 80
    70 65
    Merge Sort – Visual Example (2)
    • After the first merge we end up with half as many sublists as before the merge :
    55 75 15 20
    30 85 10 35
    40 60 25 50
    45 80 65 70
    • We again merge the susequent sorted sublists together again, thus reducing the number
    of sublists again to half :
    15 20 55 75
    10 30 35 85
    25 40 50 60
    45 65 70 80
    • Repeating the same procedure again we end up with 2 sorted sublists to be merged :
    10 15 20 30 35 55 75 85
    25 40 45 50 60 65 70 80
    • Merging these two sorted sublist together we end up with our original listed sorted! :
    10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85

    Merge Sort – Pseudo Code


    MergeSort(List[], leftIndex, rightIndex)
    Begin:
    if leftIndex < rightIndex then

    mid = (leftIndex + rightIndex) / 2


    MergeSort(List[], leftIndex, mid) // split left sublist
    MergeSort(List[], mid + 1, rightIndex) // split right sublist
    Merge(List[], leftIndex, mid, rightIndex) // merge sorted sublists
    endif
    End

    Stable Sort

    • The prime disadvantage of mergesort is that extra space


    proportional toN is needed in a straightforward
    implementation.
    •Definition: A sorting method is said to be “stable” if it
    preserves the relative order of duplicate keys in the file
    • If we have an alphabetised list of students and their year of
    graduation is sorted by year, a stable method produces a
    list in which people in the same class are still in
    alphabetical order, but a non-stable method is likely to
    produce a list with no vestige of the original alphabetic
    order.
    Merging

    • Given two ordered input files, we can combine them into one ordered output file simply by keeping
    track of the smallest element in each file and entering a loop where the smaller of the two elements is
    moved to the output.
    • If merge sort is implemented using a “stable merge”, then the result of
    the sort is stable.
    • Method of merging to be presented is “Abstract in-place merge”
    • Thisa lg o r it h m merges by copying the second array into an arraya ux
    (auxiliary array), in reverse order back to back with the first.
    • It is a stable merge procedure.

    You might also like