Can we change counting sort to sort inplace only using O(k) space where the numbers range from 1...k? The problem precisely is to design a sorting algorithm to sort 'n' records whose keys range from 1...k in O(n) time using only an auxiliary array of size k. The algorithm should sort be stable and should sort in-place. Remember that the original array is an array of records with integer keys. So simply copying the numbers won't do, we need to indeed swap the records. I know one place algo based on counting sort but it's not stable. Any solutions ?
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
