Question

Python

If it is possible, please do not use hand writing form, thank you.

Question 2: What do you know about the sorting algorithms? Explain Merge sort with example and write a Program or merge sort in any programming language.

Answer 1

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order.

Some commonly used sorting algos:

Selection Sort: time complexity  O(n²)

Bubble Sort : time complexity О(n²)

Insertion Sort: time complexity O(n*2)

Merge Sort : time complexity O(n log n)

QuickSort : time complexity O(n log n)

HeapSort: time complexity O(Logn)

MERGE SORT

Divide the unsorted list into n sublists, each comprising 1 element (a list of 1 element is supposed sorted).

p 0 q 3 1 2 r 6 7 4 5 14 7 3 12 9 11 6 2 divide p q r 0 1 2 3 p 9 r 4 5 6 7 14 7 3 12 9 11 6 2 divide r p, 0 p,q r p, 4 r 5 2,9 6 r 7 1 3 2 3 14 7 12 9 11 6 2. divide por pr 0 por 1 por 3 por 4 pir 5 por 6 por 7 N 14 7 3 12 9 11 6 2

Repeatedly merge sublists to produce newly sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

The first element of both lists is compared. If sorting in ascending order, the smaller element among two becomes a new element of the sorted list. This procedure is repeated until both the smaller sublists are empty and the newly combined sublist covers all the elements of both the sublists.

source code:-

r p, r 0 1 p, 2 p, 4 r 5 p, r 6 7 3 7 14 3 12 9 11 2 6 merge q p 0 1 2 r 2 3 р q r 4 5 6 7 3 7 12 14 2 6 9 11 merge r р 0 1 2 q 3 4 5 6 7 2. 3 6 7 9 11 12 14

def mergeSort(myList):
if len(myList) > 1:
mid = len(myList) // 2
left = myList[:mid]
right = myList[mid:]

# Recursive call on each half
mergeSort(left)
mergeSort(right)

# Two iterators for traversing the two halves
i = 0
j = 0
  
# Iterator for the main list
k = 0
  
while i < len(left) and j < len(right):
if left[i] < right[j]:
# The value from the left half has been used
myList[k] = left[i]
# Move the iterator forward
i += 1
else:
myList[k] = right[j]
j += 1
# Move to the next slot
k += 1

# For all the remaining values
while i < len(left):
myList[k] = left[i]
i += 1
k += 1

while j < len(right):
myList[k]=right[j]
j += 1
k += 1

myList = [14,7,3,12,9,11,6,2]
mergeSort(myList)
print(myList)