From the Soft Heap wikipedia page, it seems that the min extraction only takes constant time, thus using a soft heap to perform heapsort should lead to an amortized O(n). Even if the constant is large, for very large n this algorithm should be very useful. But I've never heard people mentioning this. Is there a reason that people do not use this?
Thanks!
The Soft Heap suffers from "corruption" (read the page you link to), which makes it inapplicable as a component of a general-purpose sorting routine. You will simply get the wrong answer most of the time.
If you have some application that requires a sort but could deal with the "corrupted" results you would get from a Soft Heap as part of the implementation, then this would give you a potential speedup.
The Fibonacci Heap does not suffer from "corruption," however it has a O(log n) delete time. You can use Fibonacci Heap as part of a general-purpose sorting routine, but the overall performance of your sort will be O(n log n).