MergeSort en Python

Publicado por admin en

ordenamiento mergesort

Merge sort (ordenamiento por mezcla) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás, que fue desarrollado por John Von Neumann en 1945.

En Python el algoritmo sería el siguiente:

def merge_sort(array):
   if len(array) < 2:
       return array
   else:
       pivot=len(array)/2
       left=merge_sort(array[:pivot])
       right=merge_sort(array[pivot:])
       return merge(left,right)
 
def merge(array1, array2):
   i, j = 0, 0
   result = []
 
   while(i < len(array1) and j < len(array2)):
      if (array1[i] < array2[j]):
         result.append(array1[i])
         i += 1
      else:
         result.append(array2[j])
         j += 1
 
   result += array1[i:]+array2[j:]
   return result

 


Deja un comentario