Create MergeSort.py

Thecapable · web-flow · commit 5cbdc87a6674 · 2020-10-01T01:34:59.000+05:30
diff --git a/MergeSort.py b/MergeSort.py
@@ -0,0 +1,49 @@
+def merge(left_list, right_list):
+    sorted_list = []
+    left_list_index = right_list_index = 0
+
+    left_list_length, right_list_length = len(left_list), len(right_list)
+
+    for _ in range(left_list_length + right_list_length):
+        if left_list_index < left_list_length and right_list_index < right_list_length:
+            if left_list[left_list_index] <= right_list[right_list_index]:
+                sorted_list.append(left_list[left_list_index])
+                left_list_index += 1
+            else:
+                sorted_list.append(right_list[right_list_index])
+                right_list_index += 1
+
+        elif left_list_index == left_list_length:
+            sorted_list.append(right_list[right_list_index])
+            right_list_index += 1
+
+        elif right_list_index == right_list_length:
+            sorted_list.append(left_list[left_list_index])
+            left_list_index += 1
+
+    return sorted_list
+
+
+def merge_sort(nums):
+
+    if len(nums) <= 1:
+        return nums
+
+    mid = len(nums) // 2
+
+    left_list = merge_sort(nums[:mid])
+    right_list = merge_sort(nums[mid:])
+
+    return merge(left_list, right_list)
+A=[]
+B=int(input("enter B-"))
+n=int(input("enter the number of houses "))
+for i in range(n):
+    A.append(int(input("enter the cost of the house-")))
+C = merge_sort(A)
+su=0
+ct=0
+while(su<B):
+    su=su+C[ct]
+    ct+=1
+print(ct-1)    
