3
\$\begingroup\$

Merge Sort

Merge Sort algorithm is a general-purpose comparison-based sorting algorithm. Most implementations produce a stable sort, in which the order of equal elements is preserved.

Here, our method is bottom-up merge sort algorithm, which treats the list as an array of n sublists of size 1, and iteratively doubles the size, sorts and merges the sublists.


Just for practicing, I've implemented the iterative version of merge sort algorithm, copied below, and I'd appreciate it if you'd like to review any part of it for any small or big changes/improvements.

Code

import random
from typing import TypeVar, List
from scipy import stats

T = TypeVar('T')


def iterative_merge_sort(input_list: List[T]) -> List[T]:
    """
    Iterative Bottom Up Merge Sort
    -----------------------------------------------
    Merge Sort is a Divide and Conquer algorithm.
    It divides the input array in two halves,
    calls itself for the two halves and then merges the two sorted halves.
    The merge function is used for merging two halves.

    In this algorithm, we'd start from the smallest window size of 1
    and double up the window size in each level until we'd reach to the
    last level, which would be the size of input list.

    Attributes:
    - Time Complexity: O(N*Log N)
        - In each level, there are O(N) comparisons
        - There are O(Log N) levels
    - Space Complexity: O(N) it is not an in-place sort
    - Stable Sort

    """

    # Assigns the length of input list.
    size_of_input = len(input_list)

    # Creates a new list for sorted output list.
    temp_output_list = size_of_input * [None]

    # Starts from the window size 1 and doubles up
    window_size = 1
    while window_size <= size_of_input - 1:
        sort_in_level(input_list, temp_output_list, window_size, size_of_input)
        window_size = 2 * window_size

    return temp_output_list


def sort_in_level(input_list: List[T], temp_output_list: List[T],
                  window_size: int, size_of_input: int) -> List[T]:
    """
    In this method we would assign four indices for start and end indices of two sublists:
    - Starting Index for the first sublist
    - Ending Index for the first sublist
    - Starting Index for the second sublist
    - Ending Index for the second sublist

    Then, we'd do the divide and merge
    """

    # Assigns the Starting Index of the first sublist to 0.
    first_start_index = 0
    while first_start_index + window_size <= size_of_input - 1:
        first_end_index = first_start_index + window_size - 1
        second_start_index = first_start_index + window_size
        second_end_index = second_start_index + window_size - 1

        # In case, the Second Ending Index went over the limit, which is the length of input list.
        if second_end_index >= size_of_input:
            second_end_index = size_of_input - 1

        # Merges the two sublists
        merge_sublists(input_list, temp_output_list, first_start_index,
                       first_end_index, second_start_index, second_end_index)

        # Increments the Starting Index for the first sublist for the next sublist merging
        first_start_index = second_end_index + 1

    # In case, any other element would be left, it'd be placed in the temp output list
    for i in range(first_start_index, size_of_input):
        temp_output_list[i] = input_list[i]

    # Copies to the sorted part of the output list.
    copy_sorted_list(input_list, temp_output_list, size_of_input)


def merge_sublists(input_list: List[T], temp_output_list: List[T],
                   first_start_index: int, first_end_index: int,
                   second_start_index: int, second_end_index: int) -> List[T]:
    """
    This method would merges the sublists using three simple while loops:
    - In the first while, we'd continue until the min length in between the two sublists.
    - In the second while, we'd continue if any element would be left from the sublist 1.
    - In the third while, we'd continue if any element would be left from the sublist 2.

e.g., sublist 1 [1, 3, 5, 7, 9]
e.g., sublist 2 [2, 4, 6, 8, 10, 12, 14]

- First while loop generates: [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10]
- Second while loop just passes, since no elements left from the first sublist.
- Third while loop generates: [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10, 12, 14]

    """

    # Assigns the Sublist 1 and temp output list indices (i, k)
    i = k = first_start_index
    # Assigns the Sublist 2 index (j)
    j = second_start_index

    # For if the size of smallest sublists:
    while i <= first_end_index and j <= second_end_index:
        # If the Sublist 1 element is smaller
        if input_list[i] <= input_list[j]:
            # Places the Sublist 1 element in the temp output list
            temp_output_list[k] = input_list[i]
            # Increments the Sublist 1
            i += 1
        else:
            # Places the Sublist 2 element in the temp output list
            temp_output_list[k] = input_list[j]
            # Increments the Sublist 2
            j += 1
        # Increments the temp output list
        k += 1

    # For if any element would be left in Sublist 1
    while i <= first_end_index:
        # Copies the Sublist 1 element in the temp output list
        temp_output_list[k] = input_list[i]
        # Increments the Sublist 1
        i += 1
        # Increments the temp output list
        k += 1

    # For if any element would be left in Sublist 2
    while j <= second_end_index:
        # Copies the Sublist 2 element in the temp output list
        temp_output_list[k] = input_list[j]
        # Increments the Sublist 2
        j += 1
        # Increments the temp output list
        k += 1


def copy_sorted_list(input_list, temp_output_list, size_of_input):
    """
    This method copies the sorted temp output into the input list
    """
    for i in range(size_of_input):
        input_list[i] = temp_output_list[i]


if __name__ == "__main__":

    # Creates a dash line string and a new line for in between the tests.
    delimiter = "-" * 70 + "\n"

    # Generates a random integer list.
    TEST_LIST_INTEGER = random.sample(range(-100, 100), 15) * 3
    print(f"""The unsorted integer array is:
        {TEST_LIST_INTEGER}""")
    print(delimiter)

    # Generates a random float list.
    TEST_LIST_FLOAT = stats.uniform(0, 100).rvs(45)
    print(f"""The unsorted float array is:
        {TEST_LIST_FLOAT}""")
    print(delimiter)

    # Sample float/integer test list for input.
    INTEGER_FLOAT_INPUT = list(TEST_LIST_INTEGER + TEST_LIST_FLOAT)

    # Sample float/integer test list for output.
    INTEGER_FLOAT_OUTPUT = sorted(INTEGER_FLOAT_INPUT)

    sorting_algorithms = [
        ("Iterative Merge Sort", iterative_merge_sort)
    ]

    # Testing
    for description, func in sorting_algorithms:
        if (func(INTEGER_FLOAT_INPUT.copy()) == INTEGER_FLOAT_OUTPUT):
            print(f"{description} Test was Successful.")
        else:
            print(f"{description} Test was not Successful.")
        print(f"""{description} (Integer):
            {func(TEST_LIST_INTEGER.copy())}""")
        print(f"""{description} (Float):
            {func(TEST_LIST_FLOAT.copy())}""")
        print(delimiter)

References

\$\endgroup\$
2
\$\begingroup\$

Docstrings are not comments; they exist to help the caller properly use the method.

Consider:

>>> import math
>>> help(math.log)
Help on built-in function log in module math:

log(...)
    log(x, [base=math.e])
    Return the logarithm of x to the given base.

    If the base not specified, returns the natural logarithm (base e) of x.

>>> 

This tells me how to use the function. The method used to calculate the logarithm is unimportant. It could be using a Taylor-series expansion; dunno, don't care, and it didn't tell me.

Now consider:

>>> help(iterative_merge_sort)
Help on function iterative_merge_sort in module __main__:

iterative_merge_sort(input_list: List[~T]) -> List[~T]
    Iterative Bottom Up Merge Sort
    -----------------------------------------------
    Merge Sort is a Divide and Conquer algorithm.
    It divides the input array in two halves,
    calls itself for the two halves and then merges the two sorted halves.
    The merge function is used for merging two halves.

    In this algorithm, we'd start from the smallest window size of 1
    and double up the window size in each level until we'd reach to the
    last level, which would be the size of input list.

    Attributes:
    - Time Complexity: O(N*Log N)
        - In each level, there are O(N) comparisons
        - There are O(Log N) levels
    - Space Complexity: O(N) it is not an in-place sort
    - Stable Sort

>>> 

Which parts of that help description are "helpful" to someone who wants to use this code?

  • Iterative Bottom Up Merge Sort? Nope - implementation detail.
  • Merge Sort is a Divide and Conquer algorithm ... used for merging two halves.? Nope - implementation details.
  • In this algorithm ... the size of the input list? Nope. Implementation details.
  • Time Complexity: O(N*Log N)? YES
    • In each level, there are O(N) comparisons? Nope. Implementation detail.
    • There are O(Log N) levels? Nope. Implementation detail.
  • Space Complexity: O(N) it is not an in-place sort? YES
  • Stable Sort? YES

Unanswered questions:

  • Is the sorted list in ascending or descending order?
  • Which comparison operation(s) must be defined on the elements?

Docstring should be used to describe to the user how to use the method, any requirements or preconditions, and perhaps things like what time/space resources are required. Ie)

def iterative_merge_sort(input_list: List[T]) -> List[T]:
    """
    Returns a new list of elements in ascending order; the input list is not modified.

    The list elements must implement the `<=` operator (`__le__`).  The sort is stable;
    the order of elements which compare as equal will be unchanged.

    Complexity:  Time: O(N*Log N)   Space: O(N)
    """

Implementation details, (which would be important for someone who is reviewing, maintaining or modifying the code) should be left as comments.


See sphinx-doc.org for one utility which can extract """docstrings""" to build documentation in HTML/PDF/HLP/... formats.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.