@fitzcn/

AwfulFluffyFieldmouse

Python

No description

fork
loading
Files
  • main.py
main.py
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
#http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html
def mergeSort(items):
    print("Splitting ",items)
    if len(items)>1:
    	#recursively mergesort the left and right halves
        mid = len(items)//2
        lefthalf = items[:mid]
        righthalf = items[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=0
        j=0
        k=0
        #merge items back together keeping track of position in right and left half
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                items[k]=lefthalf[i]
                i=i+1
            else:
                items[k]=righthalf[j]
                j=j+1
            k=k+1
        while i < len(lefthalf):
            items[k]=lefthalf[i]
            i=i+1
            k=k+1
        while j < len(righthalf):
            items[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",items)
    
    
#initialize a list of something, sort it, and print it
numbers = [54,26,93,17,77,31,44,55,20]
mergeSort(numbers)
print(numbers)

"""
PSEUDO CODE
continue grabbing halves of list until the half has one item
take the two smallest halfs and compare items in the same spot on each
"merge" the items according to the sort
merge up left and right sides of the list until all halves are merged
"""