Scribd
Upload
5 views3 pages

Python Sorting Algorithms Explained

The document explains two sorting algorithms in Python: Insertion Sort and Merge Sort. Insertion Sort builds a sorted list by inserting elements into their correct positions, while Merge Sort uses a Divide and Conquer approach to recursively sort and merge lists. Each algorithm is accompanied by a Python program, dry run examples, and time complexity analysis.

Uploaded by

ningthoujampunsiba21
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
5 views3 pages

Python Sorting Algorithms Explained

The document explains two sorting algorithms in Python: Insertion Sort and Merge Sort. Insertion Sort builds a sorted list by inserting elements into their correct positions, while Merge Sort uses a Divide and Conquer approach to recursively sort and merge lists. Each algorithm is accompanied by a Python program, dry run examples, and time complexity analysis.

Uploaded by

ningthoujampunsiba21
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

Sorting in Python

1. Insertion Sort

Concept:
Insertion Sort works by building the sorted list one element at a time. It takes each element
and inserts it into its correct position.

Python Program:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

Dry Run:
Input: [8, 3, 5, 2]

Pass 1: Insert 3 → [3, 8, 5, 2]


Pass 2: Insert 5 → [3, 5, 8, 2]
Pass 3: Insert 2 → [2, 3, 5, 8]

Final Output: [2, 3, 5, 8]

Time Complexity:
Best: O(n)
Average: O(n²)
Worst: O(n²)

--------------------------------------------------

2. Merge Sort

Concept:
Merge Sort follows the Divide and Conquer approach. The list is divided into halves, sorted
recursively, and merged.

Python Program:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]

merge_sort(left)
merge_sort(right)

i=j=k=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1

while i < len(left):


arr[k] = left[i]
i += 1
k += 1

while j < len(right):


arr[k] = right[j]
j += 1
k += 1

Dry Run:
Input: [6, 3, 9, 5, 2]

Divide:
[6,3] and [9,5,2]
[6] [3] [9] [5,2]
[5] [2]

Merge:
[6] + [3] → [3,6]
[5] + [2] → [2,5]
[9] + [2,5] → [2,5,9]
[3,6] + [2,5,9] → [2,3,5,6,9]
Final Output: [2, 3, 5, 6, 9]

Time Complexity:
Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)

You might also like