Programa de Python para ordenación de combinación iterativa

A continuación se muestra una implementación recursiva típica de Merge Sort que usa el último elemento como pivote.

Python

 

Python

# Recursive Python Program for merge sort
 
def merge(left, right):
    if not len(left) or not len(right):
        return left or right
 
    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j+= 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break
 
    return result
 
def mergesort(list):
    if len(list) < 2:
        return list
 
    middle = len(list)/2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
 
    return merge(left, right)
     
seq = [12, 11, 13, 5, 6, 7]
print("Given array is")
print(seq);
print("\n")
print("Sorted array is")
print(mergesort(seq))
 
# Code Contributed by Mohit Gupta_OMG

Complejidad de tiempo : O(n*log(n))
Espacio auxiliar : O(n)

¡ Consulte el artículo completo sobre Clasificación de combinación iterativa para obtener más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *