[Merge Sort , Python]

[veronica97]

Ciao a tutti,
Da poco sto studiando gli algoritmi di ordinamento, sono arrivata al Merge Sort nel quale la complessità temporale nel caso migliore e in quello peggiore è pari a $ O(nlogn) $ , il mio problema è il seguente:
Vorrei creare una lista di numeri in cui il mergesort è lento(come per esempio quando l'insertion sort è ordinato in maniera decrescente ci mette più tempo) , così da confrontarlo con una qualsiasi lista di numeri casuali e verificare che ci mette lo stesso tempo.
Vi ringrazio in anticipo se riuscite ad aiutarmi.

[apatriarca]

Il numero di confronti del merge sort è completamente indipendente dalla lista da ordinare. Non c'è alcun caso migliore o peggiore perché sono tutti esattamente uguali.

EDIT: Stavo pensando ad una variante del merge sort. Durante il merge puoi in effetti avere un numero di confronti che varia tra \(k\) e \(2\,k\) dove \(k\) è la dimensione delle sezioni della lista che stai ordinando. Il caso migliore si ha quando una sottolista viene prima dell'altra. Il caso peggiore quando devi prendere un elemento per volta da ogni lista. In altre parole il caso peggiore si ha prendendo gli elementi ordinati e dividendoli in elementi di indice pari e dispari e mettendo quindi i due insiemi uno dopo l'altro (devi fare la stessa procedura ricorsivamente ad ogni livello). Nel caso di 8 elementi avresti qualcosa come il seguente:

Codice:

1 2 3 4 5 6 7 8
1 3 5 7 | 2 4 6 8
1 5 | 3 7 || 2 6 | 4 8


[veronica97]

Grazie della risposta,
Di conseguenza una lista che impiega più tempo per essere ordinata sarebbe per esempio : 1 5 | 3 7 || 2 6 | 4 8 come mi hai detto , pero se non avessi la lista ordinata e non potrei fare il ragionamento degli indici pari/dispari ,per esempio se non so a priori gli elementi della mia lista perché gli inserisco in modo random allora posso dire che non posso definire un caso peggiore perché appunto non so quali sono gli elementi della mia lista?

[apatriarca]

Non ho capito il tuo ragionamento sinceramente. Il caso peggiore si ha quando ogni merge dell'algoritmo fa il massimo numero di confronti. Se hai una lista casuale il numero di confronti sarà compreso tra quello del caso migliore e quello del caso peggiore. Nel caso del merge sort il caso peggiore e migliore hanno la stessa complessità asintotica per cui l'algoritmo è in realtà poco dipendente dalla lista da ordinare (al contrario dell'insertion sort in cui la differenza tra i due casi è notevole).