Custom search result order by categories

Hi, I would like to make a custom query for the search results.
I want to have the search result ordered by categories in this way:

For example, this is the posts in the db:

Post1 (Cat1) – Content: example
Post2 (Cat1) – Content: example
Post3 (Cat3) – Content: example
Post4 (Cat3) – Content: example
Post5 (Cat1) – Content: example

If i search “example” i want this output:

<h2>Cat1</h2>

<p>Post1</p>
<p>Post2</p>
<p>Post5</p>

<h2>Cat3</h2>
<p>Post3</p>
<p>Post4</p>

I hope i was enough clear, anyone can help me?