Documentation in the related repo. Explained in this article.

Min operations: 3590, average: 3680

This algorithm combines the longest increasing subsequence (lis) in its ideal length (bruteforced) with the divider sort/bucket sort (depending on which one is more efficient), and the turk sort with some post-optimization and practical bruteforce recycling.

Thats essentially it but for anyone whos interested, here are some details of how it works :)

• The longest increasing subsequence is the maximum of numbers in a given randomized stack A that is already sorted (for 500 numbers, that might be around 40 that are already sorted). Depending on the set of numbers, the amount of lis that is left in a can make a big difference, so i decided to check for the best option between some sweet spot amounts that i tested beforehand and leave numbers in A accordingly.
• Next, i will either go on with the divider sort or the bucket sort, depending on which one is more efficient. I tweaked the divider sort for over a month, so theres lots of small bits that have been added, but the base is: push everything thats below the current average number value of stack A (i use indexed numbers) to B. Then i added some rules for rotation after pushing to B that made this more efficient, with many details. A parameter here is brute forced so the divider sort gets the best possible outcome. This parameter is used in different parts, so it can be recycled and work its magic repeatedly.
• Otherwise, the bucket sort, which after doing push swap for 1 month i was able to add in a day and performs better than the divider sort in about 60% of the cases, will take over. Its a regular bucket sort, so a certain range of numbers will go first, next rotation the next, etc. The first range should be the biggest with size of the buckets decreasing, so you can safe on rotation operations. The size of the buckets is brute forced.
• Afterwards, the most efficient way to push back to A with a presorted stack, the turk, is implemented. Theres many descriptions of it online.

Thanks for reading! If you have any questions regarding the push_swap, dont hesitate to ask me on slack @ltreser, im happy to help anyone who is stuck or wants to discuss optimization :)

This algorithm is a divide-and-conquer and greedy algorithm. Submitted back in Aug 2022.

It first separates elements into chunks and sorts elements back in a smart way. Also has post-optimization.

Initial state

[B]   [           A           ]
    ┋  88 41 52 20 13 65 33 71

value_as_index()
┋ 7 , 3 , 4 , 1 , 0 , 5 , 2 , 6

  ◦───────────────┐ split_a(8)
┋ 7 , 3 , 4 , 1 , 0 , 5 , 2 , 6

                  ◦───────┐ split_a(4)
  3 , 1 , 0 , 2 ┋ 6 , 7 , 4 , 5

                          ◦ split_a(2) ok
  3 , 1 , 0 , 2 , 4 , 5 ┋ 6 , 7

                  ┌───────◦ split_b(2)
  3 , 1 , 0 , 2 , 4 , 5 ┋ 6 , 7

                  ◦ split_a(2) ok
  3 , 1 , 0 , 2 ┋ 4 , 5 , 6 , 7

		  ┌───────◦ split_b(2)
  0 , 1 ┋ 3 , 2 , 4 , 5 , 6 , 7

          ◦ split_a(2)
  0 , 1 ┋ 2 , 3 , 4 , 5 , 6 , 7

  ┌───────◦ split_b(2)
  0 , 1 ┋ 2 , 3 , 4 , 5 , 6 , 7

  ◦ split_a(2) ok
┋ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7

Done

Sorts numbers 'innit?

Divide and conquer with stack-edge weighted groupings in a first step, followed by a minimum-actions based insertion in the second step.

Much more optimisations are possible.

Hard-coded solutions for small stacks are ugly, I'm so sorry.

1. Identification de la Médiane et Répartition Initiale

Objectif : Trouver la médiane des valeurs dans la pile A. Action : Transférer les éléments de la pile A à la pile B. Les éléments plus grands que la médiane sont placés au-dessus de la pile B, tandis que ceux plus petits sont placés en dessous.

2. Pré-Tri dans la Pile B

Objectif : Organiser plus finement la pile B pour faciliter le tri final. Action : Continuer à déplacer les éléments de la pile A vers la pile B. Cette étape assure que les éléments plus grands que la médiane restent au-dessus dans la pile B et les plus petits en dessous.

3. Finalisation du Tri et Rapatriement dans la Pile A

Objectif : Tri final et optimisation du placement des éléments. Action : Ramener tous les éléments de la pile B vers la pile A. À chaque transfert, l'algorithme évalue la méthode la plus efficace pour insérer l'élément dans la pile A, en minimisant le nombre d'opérations nécessaires.

turkish airlines arlgoritm turkia Çok Güzel

My first try combining bubble sort and radsort

My first algorythm. Bad but nice to see :) It sort a in b by rotating or antirotating b and pushing a.