Dynamic Sorting Algorithm (like Insertion Sort, but without knowing the number of elements)?

General
1

Hi;

There is a Rosetta Code task which has at least two implementation interpretations. One is to sort a list of integers then extract prime numbers from it. The other interpretation is to sort as part of the incoming flow. The prior interpretation is easy (too easy!) and I’ve solved it. But the second interpretation is a bit more difficult. I fiddled with it quite a bit and then I cheated and asked ChatGPT. The first response from ChatGPT didn’t work, but the subsequent fixed version seemed to do a dynamic integer insertion sort just fine. Now, I’m not going to submit this as the alternate version because I didn’t create it, ChatGPT did. I’d love to see one of you gurus just whip out a working solution and post it on Rosetta Code as second (more intelligent) solution. The Rosetta Code task named “Sort primes from list to a list“ and is found at: Sort primes from list to a list - Rosetta Code

Thanks,

RBE

2

It is OK to me, except being suboptimal. The sorted container could use binary search for insertion. The primality test should use a more efficient method. Normally first thousand or so primes are tabulated the rest is tested by Milner-Rabin algorithm. You can find both in

In this specific (meaningless) task, you can slightly rearrange things to get it much faster. Assuming that integers are small. First sort all the list. Then run the sieve (the prime test you have used) on the sorted list to pick the primes. These will be sorted. The optimisation is obvious, you run the expensive sieve only once.