algorithms-project/mergesort.py at main · bexcoding/algorithms-project · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
'''
Title: Merge Sort
Description: A sorting solution based on divide and conquer recursion
Last Updated: March 23, 2023
Developer: Alexander Beck
Email: beckhv2@gmail.com
Github: https://github.com/bexcoding

.....//\\......//\\......//\\......//\\......//\\......//\\......//\\....../
....//  \\....//  \\....//  \\....//  \\....//  \\....//  \\....//  \\....//
\..// /\ \\..// /\ \\..// /\ \\..// /\ \\..// /\ \\..// /\ \\..// /\ \\..//
\\// /  \ \\// /  \ \\// /  \ \\// /  \ \\// /  \ \\// /  \ \\// /  \ \\// /
 || | <> | || | <> |                                     > | || | <> | || |
 || | <> | || | <> | ||                          ||   // > | || | <> | || |
 /\  \  /  /\  \  /  ||                          ||  //   /  /\  \  /  /\  \
/  \  \/  /  \  \/   ||____       ___      ___   || //   /  /  \  \/  /  \
 <> | || | <> | ||   ||    \\   //   \\  //   \\ ||||    | | <> | || | <> |
 <> | || | <> | ||   ||     || ||____|| ||       || \\   | | <> | || | <> |
\  /  ||  \  /  ||   ||     || ||       ||       ||  \\  |  \  /  ||  \  /
 \/  //\\  \/  //\\  ||____//   \\___//  \\___// ||   \\ \\  \/  //\\  \/  /
    //..\\    //..\\                                      \\    //..\\    //
\  //....\\  //....\\  //....\\  //....\\  //....\\  //....\\  //....\\  //.
\\//......\\//......\\//......\\//......\\//......\\//......\\//......\\//..
'''


def combine(list1, list2, mode="standard"):
    """
    list, list -> list
    combines two sorted lists into one larger sorted list

    list1: list of numbers
    list2: list of numbers
    mode: standard is sorted in ascending order; reverse is sorted descending

    assumes list1 and list2 are already sorted and of same type
    """

    first_counter = 0
    second_counter = 0
    combined_list = []
    # check for smallest or largest item at start of each list
    while first_counter < len(list1) and second_counter < len(list2):
        if mode == "standard":
            if list1[first_counter] < list2[second_counter]:
                combined_list.append(list1[first_counter])
                first_counter += 1
            else:
                combined_list.append(list2[second_counter])
                second_counter += 1
        if mode == "reverse":
            if list1[first_counter] > list2[second_counter]:
                combined_list.append(list1[first_counter])
                first_counter += 1
            else:
                combined_list.append(list2[second_counter])
                second_counter += 1
    # when only one list remains, add the rest of its components
    while first_counter < len(list1):
        combined_list.append(list1[first_counter])
        first_counter += 1
    while second_counter < len(list2):
        combined_list.append(list2[second_counter])
        second_counter += 1
    return combined_list


def mergesort(unsorted_list, mode="standard"):
    """
    list -> list
    returns a sorted list

    unsorted_list: list of random ints, floats, or strings
    mode: standard is sorted in ascending order; reverse is sorted descending
    """

    if len(unsorted_list) <= 1:
        return unsorted_list
    else:
        half = len(unsorted_list) // 2
        return combine(mergesort(unsorted_list[:half], mode),
                       mergesort(unsorted_list[half:], mode), mode)


def reverse_mergesort(unsorted_list):
    """
    list -> list
    returns a reverse sorted list

    unsorted_list: list of random ints, floats, or strings
    """

    return mergesort(unsorted_list, "reverse")