# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="view-in-github" colab_type="text"
# <a href="https://colab.research.google.com/github/tmarissa/DATA-690-3/blob/main/DATA690_3_Assignment_7.ipynb" target="_parent"><img src="https://colab.research.google.com/assets/colab-badge.svg" alt="Open In Colab"/></a>

# + [markdown] id="4NNlA3ubQdd9"
# # Assignment 7: 
# ## Implement merge sort that uses iterations and does not depend on recursions.
#

# + [markdown] id="WsQBmW_af15-"
# # Iterative Merge Sort

# + id="WtE9745O3htz"
def merge_sort(List):
  size = 1                      # size is the beginning size
  while size < len(List) -1:    # this is a nested while loop. The outer loop is traversing for each sub array of the size
    left = 0                    # left begins from 0 and eventually should be one less than its length
    while left < len(List)-1:
      # the middle index is minimum of the left index of the subarray which is iterable and key default which is length -1
      middle = min((left + size -1), (len(List)-1))   
      # Conditional using size if 2 * size < len[List]-1 else len[List] -1
      right = ((2*size + left-1, len(List)-1)[2*size + left-1 > len(List)-1])
      # Function merge call
      merge(List, left, middle, right)
      left = left + size*2
    #Increasing sub-array size by multiple of 2 
    size = 2 * size
   
def merge(List, l, m, r):
  n1 = m-l+1    # numbers on the left
  n2 = r -m     # numbers on the right
  L = [0]* n1   # list on the left
  R = [0]* n2   # list on the right
  for i in range (0, n1):
    L[i] = List[l+i]
  for i in range(0, n2):
    R[i] = List[m + i + 1]

  i, j, k = 0, 0, l
  # Begins the comparison and sorting with conditions. Indices increment
  while i < n1 and j < n2:
    if L[i] > R[j]:
      List[k] = R[j]
      j += 1
    else:
      List[k] = L[i]
      i += 1
    k += 1
  
  while i < n1:
    List[k] = L[i]
    i +=1
    k += 1

  while j < n2:
    List[k] = R[j]
    j += 1
    k += 1


# + colab={"base_uri": "https://localhost:8080/"} id="e9DBygFbZWjs" outputId="dd6dcb16-1c2e-476e-b3ac-54d1569d206f"
List = [22, 11, 44, 55, 33]
print("List: ")
print (List)

merge_sort(List)

print("Sorted list:  ")
print(List)

# + colab={"base_uri": "https://localhost:8080/"} id="fmXT8XqPXuZO" outputId="2c1c93d2-753b-4dff-d4ad-224e5a867630"
L = [20, 51, 34, 95, 83, 15, 56, 76]
print("List:  ")
print (L)

merge_sort(L)

print("Sorted list is ")
print(L)


# + [markdown] id="SpO0wWpUe5YJ"
# ## Below is another merge sort that uses the merge from the textbook Guttag. The merge sort is iterative because there is no recursion. Both functions merge and merge sort are iterative because they don't use recursive.
# ### The merge function below uses only the left, right and compare as its parameters. Unlike the above merge which uses an array, left, right, and middle for its parameters.

# + id="rz2V7NCeX_4U"
def merge_sort2(List):
  size = 1
  while size < len(List) -1:
    left = 0
    while left < len(List)-1:
      middle = min((left + size -1), (len(List)-1))
      right = ((2*size + left-1, len(List)-1)[2*size + left-1 > len(List)-1])
      merge2(left, right, compare = lambda x, y: x <y)
      left = left + size*2
      size = 2 * size


def merge2(left, right, compare = lambda x, y: x <y):
    """Assumes left and right are sorted lists and 
       compare defines an ordering on the elements.
       Returns a new sorted (by compare) list containing
       the same elements as (left + right) would contain."""
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)) :
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result



# + colab={"base_uri": "https://localhost:8080/"} id="QmV5nVjkdnof" outputId="41c6c67b-6f48-4741-e10f-3239d9082920"
L = [20, 51, 34, 95, 83, 15, 56, 76]
print("List:  ")
print (L)

merge_sort(L)

print("Sorted list is ")
print(L)

StarcoderdataJupyterScriptsDedupFiltered