merge sort in python

Solutions on MaxInterview for merge sort in python by the best coders in the world

showing results for - "merge sort in python"
Malia
19 Oct 2020
1def merge_sort(arr):
2    # The last array split
3    if len(arr) <= 1:
4        return arr
5    mid = len(arr) // 2
6    # Perform merge_sort recursively on both halves
7    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
8
9    # Merge each side together
10    return merge(left, right, arr.copy())
11
12
13def merge(left, right, merged):
14
15    left_cursor, right_cursor = 0, 0
16    while left_cursor < len(left) and right_cursor < len(right):
17      
18        # Sort each one and place into the result
19        if left[left_cursor] <= right[right_cursor]:
20            merged[left_cursor+right_cursor]=left[left_cursor]
21            left_cursor += 1
22        else:
23            merged[left_cursor + right_cursor] = right[right_cursor]
24            right_cursor += 1
25            
26    for left_cursor in range(left_cursor, len(left)):
27        merged[left_cursor + right_cursor] = left[left_cursor]
28        
29    for right_cursor in range(right_cursor, len(right)):
30        merged[left_cursor + right_cursor] = right[right_cursor]
31
32    return merged
Bria
08 May 2017
1def mergeSort(myList):
2    if len(myList) > 1:
3        mid = len(myList) // 2
4        left = myList[:mid]
5        right = myList[mid:]
6
7        # Recursive call on each half
8        mergeSort(left)
9        mergeSort(right)
10
11        # Two iterators for traversing the two halves
12        i = 0
13        j = 0
14        
15        # Iterator for the main list
16        k = 0
17        
18        while i < len(left) and j < len(right):
19            if left[i] < right[j]:
20              # The value from the left half has been used
21              myList[k] = left[i]
22              # Move the iterator forward
23              i += 1
24            else:
25                myList[k] = right[j]
26                j += 1
27            # Move to the next slot
28            k += 1
29
30        # For all the remaining values
31        while i < len(left):
32            myList[k] = left[i]
33            i += 1
34            k += 1
35
36        while j < len(right):
37            myList[k]=right[j]
38            j += 1
39            k += 1
40
41myList = [54,26,93,17,77,31,44,55,20]
42mergeSort(myList)
43print(myList)
Hanna
18 Jan 2020
1def mergesort(list1):
2    if len(list1) >1 :
3    
4        mid = len(list1)//2
5        left_list = list1[:mid]
6        right_list = list1[mid:]
7        mergesort(left_list) #Using recursion down here for the sub list
8        mergesort(right_list) #Using recursion down here for the sub list
9        i = 0
10        j = 0
11        k = 0
12        while i<len(left_list) and j<len(right_list):
13            if left_list[i]< right_list[j]:
14                list1[k] = left_list[i]
15                i+=1
16                k+=1
17            else:
18                list1[k] = right_list[j]
19                j+=1
20                k+=1
21        while i < len(left_list): # I did this as for the end condition of above loop as when i or j will be equal to len(left/right list)  
22            list1[k] = left_list[i]
23            i+=1
24            k+=1
25
26        while j < len(right_list):
27            list1[k] = right_list[j]
28            j+=1
29            k+=1
30#Start watching from here and then as when function call will come then go check function
31n = int(input("Enter how many element you want in the list : "))
32list1 = [int(input()) for i in range(n)]
33mergesort(list1)
34print("sorted list : " + str(list1))
Kevin
09 Jan 2020
1def mergeSort(arr):
2
3    if len(arr) > 1:
4
5        a = len(arr)//2
6
7        l = arr[:a]
8
9        r = arr[a:]
10
11        # Sort the two halves
12
13        mergeSort(l)
14
15        mergeSort(r) 
16
17        b = c = d = 0
18
19        while b < len(l) and c < len(r):
20
21            if l[b] < r[c]:
22
23                arr[d] = l[b]
24
25                b += 1
26
27            else:
28
29                arr[d] = r[c]
30
31                c += 1
32
33            d += 1
34
35        while b < len(l):
36
37            arr[d] = l[b]
38
39            b += 1
40
41            d += 1
42
43        while c < len(r):
44
45            arr[d] = r[c]
46
47            c += 1
48
49            d += 1
50
51
52def printList(arr):
53
54    for i in range(len(arr)):
55
56        print(arr[i], end=" ")
57
58    print()
59 
60
61# Driver program
62
63if __name__ == '__main__':
64
65    arr = [0,1,3,5,7,9,2,4,6,866
67    mergeSort(arr) 
68
69    print("Sorted array is: ")
70
71    printList(arr)
72
73 
74
Lara
22 Oct 2016
1def mergeSort(arr): 
2    if len(arr) >1: 
3        mid = len(arr)//2 # Finding the mid of the array 
4        L = arr[:mid] # Dividing the array elements  
5        R = arr[mid:] # into 2 halves 
6  
7        mergeSort(L) # Sorting the first half 
8        mergeSort(R) # Sorting the second half 
9  
10        i = j = k = 0
11          
12        # Copy data to temp arrays L[] and R[] 
13        while i < len(L) and j < len(R): 
14            if L[i] < R[j]: 
15                arr[k] = L[i] 
16                i+= 1
17            else: 
18                arr[k] = R[j] 
19                j+= 1
20            k+= 1
21          
22        # Checking if any element was left 
23        while i < len(L): 
24            arr[k] = L[i] 
25            i+= 1
26            k+= 1
27          
28        while j < len(R): 
29            arr[k] = R[j] 
30            j+= 1
31            k+= 1
32  
33# Code to print the list 
34def printList(arr): 
35    for i in range(len(arr)):         
36        print(arr[i], end =" ") 
37    print() 
38  
39# driver code to test the above code 
40if __name__ == '__main__': 
41    arr = [12, 11, 13, 5, 6, 7]  
42    print ("Given array is", end ="\n")  
43    printList(arr) 
44    mergeSort(arr) 
45    print("Sorted array is: ", end ="\n") 
46    printList(arr)
queries leading to this page
merge sort gfgusing python how to implement the program with the program with list 2c merging 2c sorting merge sort3 way merge sort in pythonpython algo merge sor tcode merge sortmerege functions merege sortmerge sort in place pythonmergesort python codemerge sort divides the list in i two equal parts ii n equal parts iii two parts 2c may not be equal iv n parts 2c may not be equalmergesort python3merge function in python complexityunioin algothithm merge sortmerge sort speduocodemerge sort site 3arosettacode orgfuction to split the list in merge sort c languagemerge in pythonmerge algorith merge sortmerge sort python coe4 python program for merge sort merge sort divide and conquer pythonhow to use merge sort in pythonmerge sort algor3 way merge sort pythonmerge sort sorted listmerge sort simple python codemerge sortusing fucntions pythonwrite the algorithm for merge sortpython simple merge sort algorithmalgoritmi merge sorta recursive function that sorts a sequence of numbers in ascending order using the merge function above merge sort java recursive codewrite a program to implement merge sort in python marge sort in pythonmerge sort program in python 3merge sort al on pythonalgorithm for merge sort in pythonmerge code pythonmerge and sortmerge sort agorithm pythonpg2 merge sortingmerge sort on listmerge pythonmerge sort function python inbuiltpython mergesortmerge 28 29 algo in merge sortmerge sort in pythonic waymerge sort with pythontechnique of merge sortwhat is merge sort in pythonmerge sort in arraymerge sorting in pythonmerge sort code pythonsort merge in pythonpython merge sort tutorialpython code for merge sortmerge sort and time complexity in pythonsort the array using merge sort in pythonmerge sort python implementationwhat python method do merge sort on listwhich of the following functions could be used in merge sort to merge two sorted lists 3fmerge sort python best implementationmerge sort pywrite a python program to implement merge sort write c functions to sort a set of integers in descending order using top down approach of merge sortmerge sort python codemerge sort algorithm pseudocodehow merge sort in python worksmerge sort real pythonmerge sort in python 3merge sort odd numbermerge sort algorithmalgorithm paradigm of merge sort pythonmerge sort c 2b 2b global functionpython mergemerge sort array pythonalgorithm for merge sortmerge sortfunction pythonwrite a program to implement merge sort in python7th call to mergemerge lists pythonmerge how pythonquick implementation of merge sort in pythonmerge soprtmerge packages algorithms python2 way merge sort python codehow to merge sort an algorithm listmerge sort in dsmerge sort logic in pythonexamples of merge sort pythonmerge sort python codehow to write merge sort in pythonmergesort gfgpython merge sort pythonmerge sort python 3 8merge sort merge algorithmmerge sort examplesmerge sort algotithm merge sort en pythonsimple merge sort program in pythonmerge sort in pytonmerge sort algoritmomerge sorotpython merge sort functionmerge sort cppmerge sort algorihtmtechnique used in merge sortmerge sort with pyimplement merge sort pythonhow to do merge sort in pythonmerge sort python3merge sort c 2b 2b recursivemergesort oythonpython recursive merge sortcontents of array before final merge sort proceduremerge sort is also called asmerge sort implementation in c 2b 2bmerge sort python merge sort listmerge sort algo gfgno of merges require to get largest blockmerge sort in simple pythonmerge sort algorithm stepsmerge algorithm pythonmerge sort code c 2b 2bmergesort pytmerge sorty pythonmerge sort in pyhtonformula for dividing size of merge sortto sort an array of integers using recursive merge sort algorithm merfe sort pythonsimple merge sort in pythonmerge sort pythonpython function that implements a merge sortpython merge sort explainedmerge sort algorithm explainedmerge sorte pythonmerge sort in python simple programpython code for merge sort sortdescribe the concept of merge sortwrite a program include binary search and merge sort in pythonpython code datastructures mergemerge sort pyhmerge sort recursive pythona recursive function that sorts a sequence of numbers in ascending order using the merge function c 2b 2bmerge sort en pythonillustrate the operation of merge sort on the array a 3d 7b3 2c 41 2c 52 2c 26 2c 38 2c 57 2c 9 2c 49 7d explain the algorithm neatly step by step also give a graphical view of the solutionc 2b 2b recursive merge sortalgoexpert merge sort merge sort array pythonmerge sort algorithm in pythonmerge sort using queue in pythonmarge sort algorithm desgin in pythonmerge sort techniquequicksort pythonrogram for merge sort in pythonsyntax python merge sortmerge sort algo7 way split merge sortsort 28 29 in python merge sortwhat is the time complexity of a merge sort in pythonmerge sort using pythnmergesort in pythonmerge sort in python explainederge sort pythonhow to implement merge sort in pythonpython merge sort librarymerge sort pyhtonhow to merge sortedmerge sort code in pythonmerge sort chow merge sort workspseudocode for merge sortmerge function in merge sortmerge sort in python listmerge sort alogrythmmerge sort simple algopython3 mergesortnatural merge sort pythonmerge sort in python programmerge sort un c 2b 2bprogram to sort an array using merge sortworst case complexity of merge sortmarge sort in pythonpython binary search and merge sorthow many passes will be needed to sort an array which contains 5 elements using merge sortmerge array algorithm pythonpython merge osrtmerge sort descending order python geeksforgeekssorteed merge pythonmerge sort in pythonalgorithm of mergesortmerge sort function in pythonmerge sort python modulemerge sort algoithmtrace merge sort on the following set of data 3a b f z g p w s l c mmergesort with pythonpython merge sort inbuiltmerge function calgorithm sort fusion pythonmerge sort explanation in cmerge sort algorythmhow to merge sort in pythonif a merge sortt is divided into 5 parts recurrnce timemerge sort in python using functionmerge sort pytohnmerge sort geeks for geeksalgo for merge sortwhy doesn 27t python use merge sort for sort 28 29recursive merge sort ctwo way merge sort pythonworking merge sort algo examp 2cesort an array a using merge sort change in the input array itself so no need to return or print anything merge sort python 3fhow to understand to write merge sort algorithm pythonmerge sort algorithm in python with codemerge sort recursionmergesort algosort function in python uses merge sortmerge sort pseudocodemerge sort merge function pythonmergesort with odd listsmerge sort inpython2 way merge sort pythonmerge sort programmerge sort code in c 2b 2bmerge sort function ordermerge sort python programmerge function in merge sort pythonmerge list pythonmerge sort pythionexplain the concept of merge sort on the following data to sort the list 3a 27 2c72 2c 63 2c 42 2c 36 2c 18 2c 29 what is the best case and worst case time complexity of merge sort algorithm 3frecursive tree of odd even merge sortmerge sort gfg solutionmergesort python programpython merge sort codewhat is merge soermergesort algorithm pythonmerge sort using recursion cppmerge sort algotrithmalgoritma merge sortpython mege sortpython merge sort examplewrite a function called merge that takes two already sorted lists of possibility different lengths 2c and merge them into a single sorted list using sorted methodmerge sort python practiemerge sort python 5dmerge sort implementation in pythontime complexity of merge sort in pythonmergesor in pythonpython program for implementation of merge sortusing merge sort eggmerge sort code pythonmerge sort split arrays down pythonpython merge sort algorithmmerge sort python real pythonclever mergesort in pythonmerge sort by divide and conquermerge sort sort in pythonmerge sort python explanationmerge sort python recursivesorting inpython merge sortin merge sort 2c what is the worst case complexity 3ffunction mergesort 28nums 29 7b 2f 2f write merge sort code here 7dmerge sort in python in short codemerge sort algoritm explaineddecresing merge sortpython code merge sort algorithmspython complexity of merge sorthow to sort list in python using mergesortpython merge sortmerge sort codepython program for merge sortpython program for merge sort algorithmmerge sort using divide and conquer in cmerge sort for arraylist in pythonmerg sort in pythonmerge sorth in pythonprogram for merge sort in pythonpython merge sort complexitymergesort function source code stlmerge sort program in crecursive merge sort pythonpython merge sort recursive implementatonphyton merge sortmerge sort python practicepseudo code for meerge sortmerge sort in python codemerge sort examplemerge sort algorithm python line by linemerge sort python indonesiamerge sort complexity pythonmerje sort code in c 2b 2bmerge sort algorithm simple code in pythonalgoritmo merge sortmerge sort on odd number of elementspython merge sort recursionwhat is the recursive call of the merge sort in data structuremerge sort method pythonpseudocode for merge sort in pythonmerge sort implementation examplemerge sort implementation javapython code merge sortalgorithmsis merge sort in orderpython merge sort programfunction mergesort 28nums 29 7b 2f 2f write merge sort code here merge fort using pythonmerge sort source codemerge sort java recursionprogramming merge sort in pythonalgorithm of merge sort in pythonmerge sorrtmerge sort array pythonmerge sort program in pythonwrite a program to sort an array using merge sort phythonneed for sorting in merge pythonmerge sort algorithmcin pythonpythonic merge sortmerge sort using recursion pythonsort an array using recursion time complexitypython list in order mergemerge sort algorothmimplement merge sort in pythonshaker sort c geeksmerge sort in pythinmergesort recursionmergesort diagrammergesort table by element pythonmerge sort in simple pythonmergesort pyhtonbest merge sort implementationmerge sort algorithm implementation pythonmerge sort help in pythonlist merge sort explainedalready sorted order which sorting algo is best in merge sort and quick sortmerge sort javato write a python program merge sort pseudo code for merge sortmerge sort using pythonmerge sort algorithpython in place merge sortmeerge sort program to check no of passes required forr sortig an arraymerge sort c 2b 2bpython code merge fusion algorithmsmerge sort recursion pythonsample code example for merge sort in pythonmerge sort algorithm pythonmerge sort in pythonblock merge sort implementation in pythonmerge sort pythonfusion sort pythonmerge sort in c 2b 2b with proper formatmerge sort algorithm python codemerge sort complete examplemerge sort method in javamerge sor tpythontime complexity in pythonof merge sortmerge sort pseduodmerge sort in python using recursionwhat is the time complexity of traversing an array using merge sort methodmergesort 28 29 pythonpython merge sort cormenpthon merge sortmerge sort using recursion pyhtonmergesort pythonnumpy library for merge sortmergesort for pythonpython program to merge sortpython easy merge sortabout merge sort in pythonsuppose we split the elements unevenly 28not in the middle 29 when applying merge sort the resultant will be same as 3a selection sort bucket sort bubble sort insertion sortwrite an algorithm for merge sort and compute its complexity code for merge sortarray merge program in pythobpython merge sortmerge sort in an arraymerge sort pythoncode for merge sort in pythonmerge sort in python