def mergeSort(array):
          if len(array) > 1:
              #  r is the point where the array is divided into two subarrays
              r = len(array)//2
              L = array[:r]
              M = array[r:]
              # Sort the two halves
              mergeSort(L)
              mergeSort(M)
              i = j = k = 0
              # Until we reach either end of either L or M, pick larger among
              # elements L and M and place them in the correct position at A[p..r]
              while i < len(L) and j < len(M):
                  if L[i] < M[j]:
                      array[k] = L[i]
                      i += 1
                  else:
                      array[k] = M[j]
                      j += 1
                  k += 1
              # When we run out of elements in either L or M,
              # pick up the remaining elements and put in A[p..r]
              while i < len(L):
                  array[k] = L[i]
                  i += 1
                  k += 1
              while j < len(M):
                  array[k] = M[j]
                  j += 1
                  k += 1
      # Print the array
      def printList(array):
          for i in range(len(array)):
              print(array[i], end=" ")
          print()
      # Driver program
      if __name__ == '__main__':
          array = [6, 5, 12, 10, 9, 1]
          mergeSort(array)
          print("Sorted array is: ")
          printList(array)
      

      Python language logo
      Merge Sorting

      arrays
      DSA
      logic
      ...

      Merge Sort is one of the most popular sorting algorithms that is based on the principle of the Divide and Conquer Algorithms.

      A divide and conquer algorithm is a strategy for solving a large problem by

      1. breaking the problem into smaller sub-problems
      2. solving the sub-problems, and
      3. Combine them to get the desired output.

      0 Comments

        Add Comment

        Log in to add a comment

        Codiga - All rights reserved 2022.