How to handle expensive and frequent functions without blocking the main thread?

You can run the code asynchronously. This will take the same amount of time, however the code will run on a separate thread, meaning your application won't hang whilst it is running.

Setting up a thread/task is still a costly process, so I would try not to create threads every frame, instead, put delays.

For example: The A* function will be written as:

  public async void A*(List<Vector3> path)
  {
      while(!IsSorted(path) || !end)
      {
          await bogosort(path)
      }
      if(IsSorted(path))
      {
          FoundPath(path)
      }
  }

instead. Notice the async keyword before void.

Now, you'll also need to make bogosort an async method too. E.g:

 async void bogosort()
 {
      await Task.Run(() =>
      {
           // Put all code inside this block..
      });
 }

The await block allows you to wait till the code has finished execution, and the Task.Run block allows you to offload some code to another thread.

Be careful when threading code, as most of the Unity API isn't allowed to be called from another thread.

@DeanShea

For context my current solution is

 public class PathScheduler
 {
         public JobHandle current_job;
         public FindPath path;
         public Guid path_id;
     
         public void ScheduleFindPath((List<Vector3> m_list)
         {
             path = new Map.FindPath(m_list);
             path_id = path.m_id;
             current_job = path.Schedule();
             Map.FindPath.current.Add( path_id);
         }
         public void EndJob()
         {
             Map.FindPath<T>.current.Remove(path_id);
          }
 }
 public struct FindPath: IJob
 {
             public static event Action<List<Vector3>> FoundPath = delegate { };
             public static HashSet<Guid> current = new HashSet<Guid>();
             public Guid m_id;
             public FindPath(List<Vector3> given_list)
             {
                 m_id = Guid.NewGuid();
                 m_list = given_list;
             }
     
             public void Execute()
             {
                  while(!IsSorted(path) && current.Contains(m_id) )
                  {
                      bogosort(path)
                  }
                  if(IsSorted(path))
                  {
                      FoundPath(path)
                  }
             }
     }

I realise my solution isn't thread safe/best practice (using static variables in multiple threads). So far I've had no runtime errors, all the functionality and consistency that I want, no alternatives and better things to do. So if there is a solution that is thread safe, killable, doesn't block main and allows a loop to run a lot/arbitrary amount of times each frame, let me know.