Merge pull request OmkarPathak#100 from kgashok/master

Ian Doarn · web-flow · commit f04331a8ab91 · 2020-09-18T08:20:03.000-05:00
iterative mergesort added
diff --git a/pygorithm/sorting/merge_sort.py b/pygorithm/sorting/merge_sort.py
@@ -48,6 +48,26 @@ def sort(_list):
         b = sort(_list[middle:])
         return merge(a, b)
 
+from itertools import zip_longest
+def sorti(_list, verbose=True):
+    """
+    Function to sort an array
+    using merge sort algorithm, iteratively
+
+    :param _list: list of values to sort
+    :return: sorted
+    """
+    # breakdown every element into its own list
+    series = [[i] for i in _list]
+    while len(series) > 1:
+        if verbose: print(series)
+        # iterator to handle two at a time in the zip_longest below
+        isl = iter(series)
+        series = [
+            merge(a, b) if b else a
+            for a, b in zip_longest(isl, isl)
+        ]
+    return series[0]
 
 # TODO: Are these necessary?
 def time_complexities():
@@ -59,11 +79,13 @@ def time_complexities():
     return "Best Case: O(nlogn), Average Case: O(nlogn), Worst Case: O(nlogn)"
 
 
-def get_code():
+def get_code(iter=False):
     """
     easily retrieve the source code
     of the sort function
 
     :return: source code
     """
+    if iter: 
+        return inspect.getsource(sorti) + "\n"
     return inspect.getsource(sort) + "\n" + inspect.getsource(merge)
diff --git a/tests/test_sorting.py b/tests/test_sorting.py
@@ -116,6 +116,13 @@ class TestMergeSort(unittest.TestCase, TestSortingAlgorithm):
     def sort(arr):
         return merge_sort.sort(arr)
 
+class TestMergeSortIterative(unittest.TestCase, TestSortingAlgorithm):
+    inplace = False
+    alph_support = True
+
+    @staticmethod
+    def sort(arr):
+        return merge_sort.sorti(arr, verbose=False)
 
 class TestQuickSort(unittest.TestCase, TestSortingAlgorithm):
     inplace = False
