MergeSortPython/MergeSortPython.py at master · c0state/MergeSortPython · 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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

print"Initial array is:", array
print"Merged array is:", mergesort(array)
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
defmergesort(array):
iflen(array) <2:
returnarray
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
ifarr1index==len(subarray1):
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1
# array 2 fully merged take element from array 1
elifarr2index==len(subarray2):
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem <= array 2 elem
elifsubarray1[arr1index] <=subarray2[arr2index]:
mergedarray.append(subarray1[arr1index])
arr1index=arr1index+1
# both arrays still have elements but array 1 elem > array 2 elem
elifsubarray1[arr1index] >subarray2[arr2index]:
mergedarray.append(subarray2[arr2index])
arr2index=arr2index+1

returnmergedarray

if__name__=="__main__":
importrandom

array= [ random.randint(0, 100) foriinrange(0, 10) ]

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