Do you write code to sort a list these days?

Question

People in java/.net world has framework which provides methods for sorting a list.

In CS, we all might have gone through Bubble/Insertion/Merge/Shell sorting algorithms. Do you write any of it these days?

With frameworks in place, do you write code for sorting?

Do you think it makes sense to ask people to write code to sort in an interview? (other than for intern/junior developer requirement)

Answer 1

Personally, I've not had a need to write my own sorting code for a while.

As far as interview questions go, it would weed out those who didn't pay attention during CS classes.

You could test API knowledge by asking how would you build Comparable (Capital C) objects, or something along those lines.

Answer 2

I don't write the sorting algorithm, but I have implemented the IComparer in .Net for a few classes which was kind of interesting the first couple of times.

I wouldn't write the code for sorting given what is in the frameworks in most cases. There should be an understanding of why a particular sorting strategy like Quick sort is often used in frameworks like .Net.

I could see giving or being given a sorting question where some of the work is implementing the IComparer and understanding the different ways to sort a class. It would be a fairly easy thing to show someone a Bubble sort and ask, "Why wouldn't you want to do this in most applications?"

Answer 3

only on employer's interview/test =)

Answer 4

Man, if someone asked me in an interview what the best sort algorithm was, and didn't understand immediately when I said 'timsort', I'd seriously reconsider if I wanted to work there.

Timsort

This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hard-won measure of memory efficiency.

http://svn.python.org/projects/python/trunk/Objects/listsort.txt http://stackoverflow.com/questions/154504/is-timsort-general-purpose-or-python-specific

Answer 5

There are two pieces of code I write today in order to sort data

list.Sort();
enumerable.OrderBy(x => x);  // Occasionally a different lambda is used

Answer 6

I haven't really implemented a sort, except as coding exercise and to observe interesting features of a language (like how you can do quicksort on one line in Python).

I think it's a valid question to ask in an interview because it reflects whether the developer thinks about these kind of things... I feel it's important to know what that list.sort() is doing when you call it. It's just part of my theory that you should know the fundamentals behind everything as a programmer.

Answer 7

I can say with 100% certainty that I haven't written one of the 'traditional' sort routines since leaving University. It's nice to know the theory behind it, but to apply them to real-world situations that can't be done by other means doesn't happen very often (at least from my experience...).

Answer 8

I never write anything for which there's a library routine. I haven't coded a sort in decades. Nor would I ever. With quicksort and timsort directly available, there's no reason to write a sort.

I note that SQL does sorting for me.

There are lots of things I don't write, sorts being just one of them.

I never write my own I/O drivers. (Although I have in the past.)

I never write my own graphics libraries. (Yes, I did this once, too, in the '80s)

I never write my own file system. (Avoided this.)

Answer 9

There is definitely no reason to code one anymore. I think it is important though to understand the efficiency of what you are using so that you can pick the best one for the data you are sorting.

Answer 10

I work for a developer tools company, and as such I sometimes need to write new RTL types and routines. Sorting is something developers need, so it's something I sometimes need to write.

Don't forget, all that library code wasn't handed down from some mountain: some developer somewhere had to write it.

Answer 11

The way I see it, just like many others fields of knowledge, programming also has a theoretical and a practical approach to it.

The field of "theoretical programming" is the one that gave us quicksort, Radix Sort, Djikstra's Algorithm and many other things absolutely necessary to the advance of computing.

The field of "practical programming" deals with the fact that the solutions created in "theoretical programming" should be easily accessible to all in a much easier way, so that the theoretical ideas can get many, many creative uses. This gave us high-level languages like Python and allowed pretty much any language to implement packed methods for the most basics operations like sorting or searching with a good enough performance to be fit for almost everyone.

One can't live without the other... most of us not needing to hard code a sorting algorithm doesn't mean no one should.

Answer 12

I've reciently had to write a sort, of sorts. I had a list of text.. the ten most common had to show up according to the frequency at which they were selected. All other entries had to show up according to alpha sort.

It wasn't crazy hard to do but I did have to write a sort to support it.

I've also had to sort objects whose elements aren't easily sorted with an out of the box code.

Same goes for searching.. I had to walk a file and search staticly sized records.. When I found a record I had to move one record back, because I was inserting before it. For the most part it was very simple and I mearly pasted in a binary search. Some changes needed to be done to support the method of access, because I wasn't using an array that was acutally in memory.. Ah c&@p.. I could have treated it like a stream.. See now I want to go back and take a look..

Answer 13

Yes. Sometimes digging out Shell sort beats the builtin sort routine when your list is only expected to be at most a few tens of records.

Answer 14

I wrote a merge sort when I had to sort multi-gigabyte files with a custom key comparison. I love merge sort - it's easy to comprehend, stable, and has a worst-case O(n log n) performance.

I've been looking for an excuse to try radix sort too. It's not as general purpose as most sorting algorithms, so there aren't going to be any libraries that provide it, but under the right circumstances it should be a good speedup.