algorithm - Sorting n strings of size n? -

algorithm - Sorting n strings of size n? -

i want sort n strings each of length n in o(n^2) ? other solution beside radix based sorting or trie based ?

let's suppose seek using comparison-based sort. comparing 2 strings of length n takes, in worst case, time o(n). consequently, in worst case, you'd have create o(n) comparisons sort strings. however, that's impossible, since comparison-based sorting algorithms require ω(n log n) comparisons on average. worst-case can realized; starting array x1, x2, ..., xn, can form strings an-1x1, an-1x2, ..., an-1xn, , comparisons take time θ(n) each.

that rules out comparing sorts, leaves behind approaches harness actual properties of strings. approaches listed - trie-based approaches , radix sort - form basis of algorithms along these lines (in fact, best of knowledge, string sorting algorithms variations on these themes). there nicely-optimized implementations of these algorithms. example, burstsort optimized radix sort that's designed cache-friendly, , hence has improve performance naive algorithm.

one detail need maintain in mind size of alphabet strings drawn have impact on runtime. radix sort on strings of length n more takes time o(n2 + n|σ|), |σ| number of different characters strings can made from. consequently, can't utilize radix sort sort n strings of length n in time o(n2) if there way more n characters in alphabet.

algorithm sorting radix-sort