FilesExpand file tree

 master

/

merge_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

39 lines (36 loc) · 1.06 KB

 master

/

merge_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

39 lines (36 loc) · 1.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

def merge_sort(arr):

""" Merge Sort

Complexity: O(n log(n))

"""

# Our recursive base case

if len(arr)<= 1:

return arr

mid = len(arr)/2

# Perform merge_sort recursively on both halves

left, right = merge_sort(arr[mid:]), merge_sort(arr[:mid])

# Merge each side together

return merge(left, right)

def merge(left, right):

""" Merge helper

Complexity: O(n)

"""

arr = []

left_cursor, right_cursor = 0,0

while left_cursor < len(left) and right_cursor < len(right):

# Sort each one and place into the result

if left[left_cursor] <= right[right_cursor]:

arr.append(left[left_cursor])

left_cursor+=1

else:

arr.append(right[right_cursor])

right_cursor+=1

# Add the left overs if there's any left to the result

if left:

arr.extend(left[left_cursor:])

if right:

arr.extend(right[right_cursor:])

return arr

array = [1,5, 7,4,3,2,1,9,0,10,43,64]

print(array)

print(merge_sort(array, 0, len(array)-1))

print(array)