FilesExpand file tree

 master

/

MergeSortPython.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (33 loc) · 1.37 KB

 master

/

MergeSortPython.py

Copy path

Top

File metadata and controls

• Code
• Blame

38 lines (33 loc) · 1.37 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

def mergesort(array):

if len(array) < 2:

return array

else:

subarray1 = mergesort(array[:len(array)/2])

subarray2 = mergesort(array[len(array)/2:])

# merge sorted sub-arrays

arr1index = 0

arr2index = 0

mergedarray = []

while (arr1index < len(subarray1)) or (arr2index < len(subarray2)):

# array 1 fully merged take element from array 2

if arr1index == len(subarray1):

mergedarray.append(subarray2[arr2index])

arr2index = arr2index + 1

# array 2 fully merged take element from array 1

elif arr2index == len(subarray2):

mergedarray.append(subarray1[arr1index])

arr1index = arr1index + 1

# both arrays still have elements but array 1 elem <= array 2 elem

elif subarray1[arr1index] <= subarray2[arr2index]:

mergedarray.append(subarray1[arr1index])

arr1index = arr1index + 1

# both arrays still have elements but array 1 elem > array 2 elem

elif subarray1[arr1index] > subarray2[arr2index]:

mergedarray.append(subarray2[arr2index])

arr2index = arr2index + 1

return mergedarray

if __name__ == "__main__":

import random

array = [ random.randint(0, 100) for i in range(0, 10) ]

print "Initial array is:", array

print "Merged array is:", mergesort(array)