Scribd
Upload
4 views2 pages

Merge Sort Algorithm – Advanced Divide and Conquer SortingR

Merge Sort is a divide-and-conquer sorting algorithm that consistently performs well regardless of data arrangement. It involves dividing the list into halves, recursively sorting each half, and merging them back together. The algorithm has a time complexity of O(n log n) and a space complexity of O(n), while maintaining the stability of equal elements.

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
4 views2 pages

Merge Sort Algorithm – Advanced Divide and Conquer SortingR

Merge Sort is a divide-and-conquer sorting algorithm that consistently performs well regardless of data arrangement. It involves dividing the list into halves, recursively sorting each half, and merging them back together. The algorithm has a time complexity of O(n log n) and a space complexity of O(n), while maintaining the stability of equal elements.

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/ 2

1.

Introduction

Merge Sort is a powerful sorting algorithm that follows the divide-and-conquer principle.
Instead of trying to sort the whole list at once, it breaks it into smaller parts, sorts those parts, and
then combines them into a final sorted list.
It’s known for being consistent in performance regardless of the initial arrangement of data.

2. Step-by-Step Process

1. Divide: Split the list into two halves.

2. Sort: Apply Merge Sort recursively to each half.

3. Merge: Combine the two sorted halves into one sorted list.

During the merge step, elements are compared one by one from each half, and the smaller
element is placed into the new list.

3. Pseudocode

sql

CopyEdit

function mergeSort(list):

if length of list <= 1:

return list

middle = length(list) // 2

left_half = list[0:middle]

right_half = list[middle:]

left_sorted = mergeSort(left_half)

right_sorted = mergeSort(right_half)

return merge(left_sorted, right_sorted)

function merge(left, right):

result = []

while left and right are not empty:

if left[0] <= right[0]:

append left[0] to result

remove left[0] from left


else:

append right[0] to result

remove right[0] from right

append any remaining elements from left to result

append any remaining elements from right to result

return result

4. Example

Input: [42, 15, 23, 8, 4, 16]


Process:

 Split into [42, 15, 23] and [8, 4, 16]

 Recursively sort → [15, 23, 42] and [4, 8, 16]

 Merge → [4, 8, 15, 16, 23, 42]

Output: [4, 8, 15, 16, 23, 42]

5. Complexity Analysis

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

 Space Complexity: O(n)

 Stable: Yes, maintains order of equal elements

You might also like