# data[].attributes.body
https://youtu.be/Tl89Ouxr8vU

# data[].attributes.body
- Por ser um algoritmo híbrido o Tim Sort apresenta recorrência  apenas no trecho de trabalho do Merge Sort.

- A recorrência do Merger Sort é dada por: T(n) = 2 * T(n/2) + n.

- Complexidade assintótica do Tim Sort: O(n log(n)).
- Complexidade de espaço: O(n).

# data[].attributes.body
https://github.com/jytaloramon/data-structure/blob/feature/sort/src/tim_sort.c

# data[].attributes.attachment_link.description
You can't perform that action at this time. You signed in with another tab or window. You signed out in another tab or window. Reload to refresh your session. Reload to refresh your session.

# data[].attributes.headline
Funcionamento do algoritmos sobre um conjunto de dados:

# data[].attributes.subject
Funcionamento do algoritmos sobre um conjunto de dados:

# data[].attributes.body
https://www.youtube.com/watch?v=NVIjHj-lrT4&ab_channel=TimoBingmann

# data[].attributes.body
https://github.com/jytaloramon/data-structure/blob/feature/sort/src/main_sort_tests.c

# data[].attributes.attachment_link.description
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters You can't perform that action at this time. You signed in with another tab or window.

# data[].attributes.body
* Resultado marcados com "----" significam que o teste não pode ser concluído no tempo estipulado de 1h.

# data[].attributes.body
Criado por Tim Peters em 2002, o algoritmo de ordenação TimSort é um híbrido e estável algoritmo de classificação, derivado dos algoritmos de ordenação Merge Sort e Insertion Sort, ele projetado para funcionar bem em muitos tipos de dados do mundo real, partindo da premissa que, na maioria das vezes, eles apresentam subsequências de dados que já estão ordenados por certo critério.

Inventado por Tim para ser usado na linguagem de programação Python, esse algoritmo de ordenação é padrão da linguagem desde a versão 2.3. Ele atualmente, também é usado para ordenar arrays na plataforma Java SE.

# data[].attributes.headline
Tim descreve seu algoritmos da seguinte forma: 

# data[].attributes.subject
Tim descreve seu algoritmos da seguinte forma: 

# data[].attributes.body
[...] um adaptativo, estável, Merge Sort natural, modestamente chamado de TimSort (hey, eu mereço). Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente sintonizado, híbrido, SampleSort de Python em matrizes aleatórias. Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores "inteligentemente". Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória

# data[].attributes.body
https://en.wikipedia.org/wiki/Tim_Peters_(software_engineer)

# data[].attributes.attachment_link.title
Tim Peters (software engineer) - Wikipedia

# data[].attributes.body
https://www.chrislaux.com/timsort.html

# data[].attributes.attachment_link.readable_text
Click here to see sorted array Click here to load new random array

Timsort is a hybrid sorting algorithm designed by Tim Peters for the Python language, but now also used in Java and Android, amongst others. Hybrid means that multiple sorting techniques are blended into one algorithm for good real-world performance. The main ingredients are Insertion sort and Mergesort. But Timsort also works with the technique of identifying pre-existing runs in the input data.

The panel above shows a random array with runs highlighted in colour. We have tweaked the random array generator a little, to have more and longer runs present than in purely random data. Runs are existing parts of the array that are already sorted as desired. Ascending runs are shown in green and descending runs are shown in red. Such runs are often present in arrays to be sorted in practice, depending on the type of data. In some cases only a few individual values are not yet sorted to the right position.

Finding runs

This panel shows how the runs are identified. This is a pretty straightforward step: simply compare the next element to the previous one and see if it is part of an existing run, or whether the run is over. The bold bars superimposed on the array mark the boundaries of runs.

Reversing runs

Once the runs are identified, there is another simple and fast step to perform: reverse all those runs that are counter to the desired sort order, in this case we want to reverse the descending runs. The panel above shows an array with the runs already identified, and proceeds to reverse the descending runs. Note that in descending runs, successive but equal values can't be part of the same run. This is the first step in the algorithm that makes Timsort 'stable', meaning that a pre-existing ordering is maintained for equal values. As descending runs are reversed, equal values can't be in the same run.

Ready to sort Finding runs Reversing runs Merging runs Sorting complete

Natural Mergesort

At this point it is possible to sort the entire array, without any further Timsort magic, just by merging the unsorted portions of the array with the runs. We call this 'natural Mergesort'. This is displayed on this panel, starting with an unsorted array, finding and possibly reversing runs, all the way to merging the runs to obtain a sorted array. But this was just an aside, and on the following panels we will continue with the Timsort strategy from after reversing our runs.

Ready to sort Finding run Reversing run Insertion sort on run Steps complete

Minrun

Timsort has a parameter called 'minrun'. This is the minimum size a run should have before moving on to the next stage of merging runs. This size requirement is achieved by running Insertion sort on a run, adding following input elements to a run, until the minimum size is reached. This is very efficient, because Insertion sort is fast for small input sizes.

Minrun is chosen as a function of the input size, at the start of the algorithm, and is at least 32. Here we have lowered this value to 11, in order to illustrate the operation of Timsort on the small arrays we can display here. The last run may of course have fewer elements than minrun.

Ready to sort Finding run Reversing run Insertion sort on run Merging high Merging low Sort complete

Timsort

Here we display the entire operation of Timsort on a larger array of 71 values, for better illustration. After finding and possibly reversing runs, and using Insertion sort to increase their size to at least minrun (= 11), the final step of Timsort is carried out: merging. A stack, shown here at the bottom right, keeps track of the positions of merged runs, in the order they are present in the array. As new runs are discovered, they are added to the top of the stack.

There are two main invariants that are maintained by Timsort: the sum of the lengths of the last two runs has to be smaller than the one previous to them, and the length of the last entry has to be smaller than its predecessor. When one of the invariants is violated, this leads to neighboring runs being merged into one, as in Mergesort. The stack is used to keep track of all this. To merge, the smaller of the two runs is temporarily moved into temp space, shown here at the bottom left. Depending on the position of the free space, resulting from using the temp space, Timsort merges either 'low' or 'high', both of which can be observed on this panel with enough patience.

Ready to sort Finding run Reversing run Insertion sort on run Merging high Merging low Sort complete

Sorting an interesting array

This panel shows the entire Timsort operation as on the previous panel, but on a larger array of 128 values, and at a faster speed. Minrun was set to 8 for illustration. Here we have generated input data which illustrates the complexity of merging natural runs better. Using the merge stack makes sure that runs of similar size are merged with preference before the resulting run is merged with larger runs further up. This yields better performance.

So why is Timsort fast? First off, very small input arrays are simply insertion sorted, which is efficient for small sizes. Next, existing runs in the input are identified and used, all the way up to the case where the input is already sorted and needs no modification. This adds up quite fast for the handling of many cases. Finally, Mergesort is aymptotically fast for large input arrays, which is what Timsort reduces to in the case of large, random input.

Ready to sort Finding run Reversing run Insertion sort on run Merging high Merging low Sort complete

Presorted input

Finally, this panel shows the example of running Timsort on partially presorted input. The sorted array above has had a small number of random values concatenated to its end, and requires sorting again. This could be easily handled by plain Insertion sort, but the more general Timsort recognises the situation by identifying the main run and handles the input pretty efficiently.

I just want to mention how the animated implementation shown here deviates from the Python original. I have already spoken about the minrun parameter, which was artificially lowered. In addition, the Insertion sort used in the original is so-called 'binary' Insertion sort, here we have used a simpler swap-based variant. Next, the original code has a 'galloping mode' during merging, which we have not shown here at all. Galloping is used when the next element of one run is not taken until many elements from the other run have been transferred, to speed things up.

If you speak the language C you can have a look at the original implementation for Python here (starting at line 2162).

Sources

Impressum | Privacy policy | Email | Copyright © 2019-2020 Christopher Laux

# data[].attributes.attachment_link.description
Click here to see sorted array Click here to load new random array Timsort is a hybrid sorting algorithm designed by Tim Peters for the Python language, but now also used in Java and Android, amongst others. Hybrid means that multiple sorting techniques are blended into one algorithm for good real-world performance.

# data[].attributes.body
https://medium.com/@rylanbauermeister/understanding-timsort-191c758a42f3

# data[].attributes.attachment_link.readable_text
Sorting algorithms are an awkward combination of fundamentally necessary, and deeply contentious. From new engineers looking to impress in an interview to older engineers searching out a solution to a rapidly scaling database, there are myriad factors to take into consideration. What is the speed of comparison between two objects? What's the swap time? How large is the database? What type of objects does it contain? Is it already semi-sorted? Do the...

# data[].attributes.attachment_link.description
Sorting algorithms are an awkward combination of fundamentally necessary, and deeply contentious. From new engineers looking to impress in an interview to older engineers searching out a solution to a rapidly scaling database, there are myriad factors to take into consideration. What is the speed of comparison between two objects?

# data[].attributes.body
https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399

# data[].attributes.attachment_link.readable_text
Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world - not constructed in academia.
Click here to view the updated article:
Timsort is a sorting algorithm that is efficient for real-world data and not created in an academic laboratory. Tim Peters created Timsort for the Python programming language in 2001. Timsort first analyses the list it is trying to sort and then chooses an approach based on the analysis of the list.

Since the algorithm has been invented it has been used as the default sorting algorithm in Python, Java, the Android Platform, and in GNU Octave.

Timsort's big O notation is O(n log n). To learn about Big O notation, read this.

Timsort's sorting time is the same as Mergesort, which is faster than most of the other sorts you might know. Timsort actually makes use of Insertion sort and Mergesort, as you'll see soon.

Peters designed Timsort to use already-ordered elements that exist in most real-world data sets. It calls these already-ordered elements "natural runs". It iterates over the data collecting the elements into runs and simultaneously merging those runs together into one.

The array has fewer than 64 elements in it

If the array we are trying to sort has fewer than 64 elements in it, Timsort will execute an insertion sort.

An insertion sort is a simple sort which is most effective on small lists. It is quite slow at larger lists, but very fast with small lists. The idea of an insertion sort is as follows:

Look at elements one by one

Build up sorted list by inserting the element at the correct location

Here's a trace table showing how insertion sort would sort the list [34, 10, 64, 51, 32, 21]

In this instance we are inserting the newly sorted elements into a new sub-array, which starts at the start of the array.

Here's a gif showing insertion sort:

More about runs

If the list is larger than 64 elements than the algorithm will make a first pass through the list looking for parts that are strictly increasing or decreasing. If the part is decreasing, it will reverse that part.

So if the run is decreasing, it'll look like this (where the run is in bold):

If not decreasing, it'll look like this:

The minrun is a size which is determined based on the size of the array. The algorithm selects it so that most runs in a random array are, or become minrun, in length. Merging 2 arrays is more efficient when the number of runs is equal to, or slightly less than, a power of two. Timsort chooses minrun to try to ensure this efficiency, by making sure minrun is equal to or less than a power of two.

The algorithm chooses minrun from the range 32 to 64 inclusive. It chooses minrun such that the length of the original array, when divided by minrun, is equal to or slightly less than a power of two.

If the length of the run is less than minrun, you calculate the length of that run away from minrun. Using this new number, you grab that many items ahead of the run and perform an insertion sort to create a new run.

So if minrun is 63 and the length of the run is 33, you do 63-33 = 30. You then grab 30 elements from in front of the end of the run, so this is 30 items from run[33] and then perform an insertion sort to create a new run.

After this part has completed we should now have a bunch of sorted runs in a list.

Merging

Timsort now performs mergesort to merge the runs together. However, Timsort makes sure to maintain stability and merge balance whilst merge sorting.

To maintain stability we should not exchange 2 numbers of equal value. This not only keeps their original positions in the list but enables the algorithm to be faster. We will shortly discuss the merge balance.

As Timsort finds runs, it adds them to a stack. A simple stack would look like this:

Imagine a stack of plates. You cannot take plates from the bottom, so you have to take them from the top. The same is true about a stack.

Timsort tries to balance two competing needs when mergesort runs. On one hand, we would like to delay merging as long as possible in order to exploit patterns that may come up later. But we would like even more to do the merging as soon as possible to exploit the run that the run just found is still high in the memory hierarchy. We also can't delay merging "too long" because it consumes memory to remember the runs that are still unmerged, and the stack has a fixed size.

To make sure we have this compromise, Timsort keeps track of the three most recent items on the stack and creates two laws that must hold true of those items:

1. A > B + C

2. B > C

Where A, B and C are the three most recent items on the stack.

In the words of Tim Peters himself:

What turned out to be a good compromise maintains two invariants on the stack entries, where A, B and C are the lengths of the three righmost not-yet merged slices

Usually, merging adjacent runs of different lengths in place is hard. What makes it even harder is that we have to maintain stability. To get around this, Timsort sets aside temporary memory. It places the smaller (calling both runs A and B) of the two runs into that temporary memory.

Galloping

While Timsort is merging A and B, it notices that one run has been "winning" many times in a row. If it turned out that the run A consisted of entirely smaller numbers than the run B then the run A would end up back in its original place. Merging the two runs would involve a lot of work to achieve nothing.

More often than not, data will have some preexisting internal structure. Timsort assumes that if a lot of run A's values are lower than run B's values, then it is likely that A will continue to have smaller values than B.

Timsort will then enter galloping mode. Instead of checking A[0] and B[0] against each other, Timsort performs a binary search for the appropriate position of b[0] in a[0]. This way, Timsort can move a whole section of A into place. Then Timsort searches for the appropriate location of A[0] in B. Timsort will then move a whole section of B can at once, and into place.

Let's see this in action. Timsort checks B[0] (which is 5) and using a binary search it looks for the correct location in A.

Well, B[0] belongs at the back of the list of A. Now Timsort checks for A[0] (which is 1) in the correct location of B. So we're looking to see where the number 1 goes. This number goes at the start of B. We now know that B belongs at the end of A and A belongs at the start of B.

It turns out, this operation is not worth it if the appropriate location for B[0] is very close to the beginning of A (or vice versa). so gallop mode quickly exits if it isn't paying off. Additionally, Timsort takes note and makes it harder to enter gallop mode later by increasing the number of consecutive A-only or B-only wins required to enter. If gallop mode is paying off, Timsort makes it easier to reenter.

In short, Timsort does 2 things incredibly well:

Great performance on arrays with preexisting internal structure

Being able to maintain a stable sort

Previously, in order to achieve a stable sort, you'd have to zip the items in your list up with integers, and sort it as an array of tuples.

Code

If you're not interested in the code, feel free to skip this part. There's some more information below this section.

The sourcecode below is based on mine and Nanda Javarma's work. The source code is not complete, nor is it similar to Python's offical sorted() source code. This is just a dumbed-down Timsort I implemented to get a general feel of Timsort. If you want to see Timsort's original source code in all its glory, check it out here. Timsort is offically implemented in C, not Python.

Timsort is actually built right into Python, so this code only serves as an explainer. To use Timsort simply write:

Or

If you want to master how Timsort works and get a feel for it, I highly suggest you try to implement it yourself!

This article is based on Tim Peters' original introduction to Timsort, found here.

Did you like this article? Connect with me on Social Media to discuss all things computer science related 😁

Don't forget to click that 👏clap👏 button to show your appreciation!

I didn't get paid for writing this article. If you want to support me, feel free to buy me a coffee or something below 😁

# data[].attributes.attachment_link.title
Timsort - the fastest sorting algorithm you've never heard of | HackerNoon

# data[].attributes.attachment_link.description
Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world - not constructed in academia. Click here to view the updated article: Timsort is a sorting algorithm that is efficient for real-world data and not created in an academic laboratory. Tim Peters created Timsort for the Python programming language in 2001.

# data[].attributes.body
https://bugs.python.org/file4451/timsort.txt

# data[].attributes.body
https://pt.wikipedia.org/wiki/Merge_sort#Demonstra.C3.A7.C3.A3o_da_complexidade_de_tempo

# data[].attributes.attachment_link.readable_text
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar.

Sua ideia básica consiste em Dividir (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas). Como o algoritmo Merge Sort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas.

Os três passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante ;

2. Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com para o tempo de execução;

3. Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo

Complexidade

Complexidade de tempo: .

Complexidade de espaço: .

Para que teremos que fazer com que

Então:

Em comparação a outros algoritmos de divisão e conquista, como o Quicksort, o Merge apresenta a mesma complexidade. Já em comparação a algoritmos mais básicos de ordenação por comparação e troca ( bubble, insertion e selection sort), o Merge é mais rápido e eficiente quando é utilizado sobre uma grande quantidade de dados. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.

A sua eficiência é a mesma para melhor, pior e caso médio, independentemente de como os dados do array estão organizados a ordenação será eficaz.

Obs.: O Bubble sort apresenta melhor caso como porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa [3] . O Quick sort pode atingir um tempo de em um caso específico quando o particionamento é desequilibrado.

É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a .

É um algoritmo estável na maioria das implementações, em que elas podem ser iterativas ou recursivas.

É possível também implementar o algoritmo com espaço adicional .

Algoritmo Criado por Von Neumann em 1945.

Desvantagens

Utiliza funções recursivas;

Gasto extra de memória. O algoritmo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a .

função mergesort (vetor a)
     se (n == 1) retornar a

     vetor l1 = a[0] ... a[n/2]
     vetor l2 = a[n/2 + 1] ... a[n]

     l1 = mergesort(l1)
     l2 = mergesort(l2)

     retornar mesclar(l1, l2)
fim da função mergesort

função mesclar (vetor a, vetor b)
     vetor c

     enquanto (a e b têm elementos)
          if (a[0] > b[0])
               adicionar b[0] ao final de c
               remover b[0] de b
          senão
               adicionar a[0] ao final de c
               remover a[0] de a
     enquanto (a tem elementos)
          adicionar a[0] ao final de c
          remover a[0] de a
     enquanto (b tem elementos)
          adicionar b[0] ao final de c
          remover b[0] de b
     retornar c
fim da função mesclar

Outra implementação em C++:

Referências

# data[].attributes.attachment_link.title
Merge sort - Wikipédia, a enciclopédia livre

# data[].attributes.attachment_link.description
O merge sort , ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar. Sua ideia básica consiste em Dividir (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas).

# data[].attributes.headline
Implementação passo a passo do Tim Sort (inglês)

# data[].attributes.subject
Implementação passo a passo do Tim Sort (inglês)

# data[].attributes.attachment_link.title
Tim Sort Algorithm in Python With Program

# data[].attributes.headline
Artigo sobre as estratégias de Mergesort e Timsort

# data[].attributes.subject
Artigo sobre as estratégias de Mergesort e Timsort

# data[].attributes.attachment_link.title
Merge Strategies: from Merge Sort to TimSort

# data[].attributes.attachment_link.description
The introduction of TimSort as the standard algorithm for sorting in Java and Python questions the generally accepted idea that merge algorithms are not competitive for sorting in practice. In an at- tempt to better understand TimSort algorithm, we define a framework to study the merging cost of sorting algorithms that relies on merges of monotonic subsequences of the input.

# data[].attributes.headline
Implementação do Timsort e Mergesort utilizando síntese de alto nível

# data[].attributes.subject
Implementação do Timsort e Mergesort utilizando síntese de alto nível

# data[].attributes.attachment_link.title
An Efficient Hardware Implementation of TimSort and MergeSort Algorithms Using High Level Synthesis

# data[].attributes.attachment_link.description
Sorting algorithms are one of the most commonly used in computer science. They can be seen as a pillar for some applications such as decision support systems, path planning, etc. However, sorting large number of elements needs high computation rate. Consequently, accelerating sorting algorithms using hardware implementation is an interesting solution to speed up computations.

# data[].attributes.body
Execução em C:

I. Faça o clone do projeto. $ git clone https://github.com/jytaloramon/data-structure.git
II. Entre na pasta Sort.
III. $ git checkout feature
IV. Gere os dataset: $ python src/generate_dataset.py
V. Execute os seguintes comandos em ordem:
- $ make
- $ make main_sort_tests
- $ ./build/main_sort_tests

Execução em Python:
- Apenas acessar o link e apertar "play"

# data[].attributes.attachment_link.description
Algoritmos e Estrutura de Dados. Contribute to jytaloramon/data-structure development by creating an account on GitHub.

# data[].attributes.headline
Tabela comparativa entre o custo dos algoritmos

# data[].attributes.subject
Tabela comparativa entre o custo dos algoritmos

# data[].attributes.body
Fonte: https://ronanlopes.me/implementacao-em-python-e-analise-dos-algoritmos-de-ordenacao-insertionsort-mergesort-e-timsort/

# data[].attributes.body
Configuração da Máquina:
- Processador: Intel I5 8265U @3.9GHz.

- Memória RAM: 20GB Dual Channel 2400mhz.

- SO: Arch Linux x86_64 @Kernel: 5.16.2-arch1-1

- Linguagem usada: C-Language

# data[].attributes.body
Segue um paradigma híbrido derivado de ordenação por inserção - Insertion Sort - e por mesclagem/divisão e conquista - devido ao Merge Sort.

# data[].attributes.body
I. Algoritmo Im-place?
O algoritmo Tim Sort apresentado não é um algoritmo Im-place, pois o Merge Sort implementado apresenta uma classificação por mesclagem padrão requerendo um armazenamento adicional O(n) para realizar a mesclagem.

Vale ressaltar que existem formas alternativas de implementação do Merge Sort Im-place.

II. Tipo de Ordenação:
Devido o uso do Merge Sort com sua classificação por mesclagem o algoritmo Tim Sort apresenta um método de classificação externa pois é necessário um array/memória auxiliar para  acomodar temporariamente os dados para concluir seu processo.

III. Estabilidade:
O Tim Sort é um algoritmo  classificação estável pois tanto o Insertion quanto o Merge Sort são método estáveis.

# data[].attributes.body
- Descendente: os dados apresentam-se ordenados de totalmente inverso do estado desejado.

- Ascendente: os dados apresentam-se já ordenados, ou seja, já estão no estado desejado.

- Aleatório: os apresentam-se de forma totalmente sem padrão.

- Seccionado: construído com base em um conglomerado de intervalos de no máximo 32 elementos. Cada intervalo é chamados de secção e podem ser ou descendente ou ascendente  ou aleatório. Após a geração de cada secção, elas são agrupadas com as outras e formam o dataset final.

# data[].attributes.body
https://wiki.c2.com/?TimSort

# data[].attributes.attachment_link.description
TimSort is an adaptive, stable, in-place sorting algorithm developed by TimPeters.

# data[].attributes.body
https://www.youtube.com/watch?v=79buQYoWszA&ab_channel=Programa%C3%A7%C3%A3oDescomplicadaLinguagemC

# data[].attributes.attachment_link.title
[ED] Aula 49 - Ordenação - InsertionSort

# data[].attributes.body
https://youtu.be/ekxvb3Q5hE4

# data[].attributes.body
A partir dos gráficos mostrado fica evidente que o Tim Sort é o melhor algoritmo dos 3. Em relação ao tempo, com exceção da configuração Descendente que houve vitória do Merge Sort, todas as outras configurações manteve a seguinte ordem:

1. Tim Sort
2. Merge Sort
3. Insertion Sort.

Já em relação as operações, em geral o Merge Sort fazia menos operações que o Tim Sort, mesmo assim seu desempenho é pior e isso pode ser justificado pelo tempo das trocas que no Tim Sort é feita de forma mais inteligente.

# data[].attributes.headline
Execução Para Entradas Aleatórias - Python

# data[].attributes.subject
Execução Para Entradas Aleatórias - Python

# data[].attributes.headline
Execução Para entradas Ordenadas de Forma Ascendente - Python

# data[].attributes.subject
Execução Para entradas Ordenadas de Forma Ascendente - Python

# data[].attributes.headline
Universidade Federal de Alagoas - Campus Arapiraca

# data[].attributes.subject
Universidade Federal de Alagoas - Campus Arapiraca

# data[].attributes.body
Equipe:
- Gean L. Freire P. Santos
- José Y. Ramon de A. Gonçalves

Curso: Ciência da Computação
Disciplina: Projeto e Análise de algoritmos.
Professor: Alexandre Paes.

# data[].attributes.body
Diante dos resultados é possível perceber que o algoritmo Tim Sort de fato se sair melhor quanto maior e mais frequente for os intervalos ordenados.

Sendo assim, a ordem do melhor para o pior resultado em relação ao tempo ficou:

1. Ascendente
2. Descendente
3. Seccionado
4. Aleatório.

Do melhor para o pior resultado em relação as operações:

1. Descendente
2. Ascendente
3. Seccionado
4. Aleatório.