Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Jawad Presentation 1

    Uploaded by

    IT LAb 2
    The document discusses merge sort, including its steps of divide, conquer, and merge. It provides details on the time and space complexity of merge sort as well as its advantages of stability and guaranteed worst-case performance and disadvantages of additional space usage and being non-in-place.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Jawad Presentation 1

    Uploaded by

    IT LAb 2
    12 views11 pages
    The document discusses merge sort, including its steps of divide, conquer, and merge. It provides details on the time and space complexity of merge sort as well as its advantages of stability and guaranteed worst-case performance and disadvantages of additional space usage and being non-in-place.

    Original Description:

    dsa

    Original Title

    jawad presentation 1

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses merge sort, including its steps of divide, conquer, and merge. It provides details on the time and space complexity of merge sort as well as its advantages of stability and guaranteed worst-case performance and disadvantages of additional space usage and being non-in-place.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    12 views11 pages

    Jawad Presentation 1

    Uploaded by

    IT LAb 2
    The document discusses merge sort, including its steps of divide, conquer, and merge. It provides details on the time and space complexity of merge sort as well as its advantages of stability and guaranteed worst-case performance and disadvantages of additional space usage and being non-in-place.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 11

    MERGE SORT DATA STRUCTURE

    AND AGORITHMS TUTUORIALS

    • Presented By: Jawad Sharafat


    • (MIS I’D : 39308)
    • Department of Computer Science
    • (Date: 29/04/2024)
    • Presented To: Mr. Muhammad Adil
    • Department of Computer Science

    • Federal Urdu University of Arts, Science & Technology, Islamabad-Pakistan

    3
    MERGE SORT:
    • Merge sort is a sorting algorithmthat follow
    the divide–and–conquer approach . It works
    by recursively dividing the input array into
    smaller aubarrays and sorting those subarrays
    then merging them back to obtain the sorted
    array.
    • In simple terms , we can say that the process of
    merge sort is to divide the array into two
    halves ,sort each half , and then merge the
    sorted halves back together. The process is
    repeated untill the entire array is sorted.
    STEP BY STEP EXPLANATION
    OF MERGE SORTING
    1. Divide: Divide the list or array recursively
    into two halves untill it can no more be
    divided.
    2. Conquer: Each subarray is sorted
    individually using the merge sort algorithm.
    3. Merge: The sorted subarrays are merged
    back together in sorted order. The process
    continues untill all elements from both
    subarrays have been merged.
    COMPLEXITY ANALYSIS OF
    MERGE SORT
    Time Complexity
    • Best Case: 0(n log n), When the array is already sorted or nearly sorted.
    • Average Case: 0(n log n), When the array is randomly ordered.
    • Worst Case: 0(n log n), When the array is sorted in reverse order.
    Space Complexity: 0(n) Additionally sapce required for the temporary array
    used during merging.
    ADVANTAGES OF MERGE
    SORT
    • Stability: Merge sort is a stable sorting algorithm , which means it
    maintains the relative order of equal elements in the input array.
    • Guaranteed worst-case performance: Merge sort has a worst-case time
    compexity of 0(N logN), which it perform well even on large dataset.
    • Simple to implement: The divide-and-conquer approach is straightforward.
    DISADVANTAGES OF MERGE
    SORT
    • Space Complexity: Merge sort requires additional mmemory to store the
    merged sub-arrays during the sorting process.
    • Not in-place: Merge sort is not an in-place soring algorithm, which means it
    requires additionally memory to store the sorted data. This can be a
    disadvantage in applications where memory usage is a concern.
    APPLICATIONS OF MERGE
    SORT
    • Sorting large dataset.
    • External sorting (when the dataset is too large to fit in memory).
    • Invertion counting (counting the number of inversion in an array).
    • Finding the median of an array.
    Any Question ?
    Thank
    You !

    You might also like