Scribd
Upload
3 views1 page

Merge Sort Algorithm – Divide and Conquer Sorting

Merge Sort is a divide-and-conquer algorithm that efficiently sorts large datasets by recursively dividing the list into halves, sorting them, and merging them back together. The pseudocode outlines the procedure for implementing Merge Sort, while an example demonstrates its functionality. The algorithm has a time complexity of O(n log n) and a space complexity of O(n), and it is stable.

Uploaded by

rohitmishra007776
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views1 page

Merge Sort Algorithm – Divide and Conquer Sorting

Merge Sort is a divide-and-conquer algorithm that efficiently sorts large datasets by recursively dividing the list into halves, sorting them, and merging them back together. The pseudocode outlines the procedure for implementing Merge Sort, while an example demonstrates its functionality. The algorithm has a time complexity of O(n log n) and a space complexity of O(n), and it is stable.

Uploaded by

rohitmishra007776
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

1.

Introduction

Merge Sort is a divide-and-conquer sorting algorithm. It splits the list into smaller parts, sorts
them, and then merges them back together. It is efficient for large datasets.

2. How It Works

1. Divide the array into two halves.

2. Recursively sort each half.

3. Merge the sorted halves into a single sorted array.

3. Pseudocode

sql

CopyEdit

procedure mergeSort(A):

if length(A) > 1:

mid = length(A) // 2

left = A[0...mid-1]

right = A[mid...end]

mergeSort(left)

mergeSort(right)

merge(left, right, A)

4. Example

Input: [38, 27, 43, 3, 9, 82, 10]


Output: [3, 9, 10, 27, 38, 43, 82]

5. Complexity Analysis

 Time Complexity: O(n log n) in all cases

 Space Complexity: O(n) extra space

 Stability: Stable

You might also like