First off, if this is in the wrong place I apologise. I wasn’t too sure on which of the Stack Exchange sites to ask it.
I am studying Software Development at university, on a one year conversion course. My main programming language is Java. We have just finished studying searches and sorts. Focussing on the latter in particular, I had a hard time working through the intricacy of the code. Some, like an insertion sort, were obvious enough. Others, like the merge sort, I found extremely tricky to get my head around. I understand totally how they work, I just wouldn’t want to implement my own.
I’ve been told most programmers don’t create their own sorts/searches as the built in methods in Java are more reliable and generally faster. However, it’s considered good practice to know these sorts.
When I look at a sort like the merge sort, or binary sort, I think to myself that I could never have come up with such solutions. They are too intricate and complicated.
This brings me to my question. Do most programmers use sorts like people use simple Maths formulae, e.g. the area of a triangle or circle, where you apply it almost mesmerically? As a programmer would you put any real effort into trying to develop new, or more efficient sorts? Or if you knew a sort was needed would you simply know which was better through the bigOh notation and then just copy and paste the same thing in, without ever really thinking about the coding behind it?
Note: if this question is not fit for Q&A (I did look at the FAQ and I think it is), please advise me where I could post. Thank you.
8
Folks obsess about sorting algorthims for the wrong reasons. The value of understanding mergesort or any other sort isn’t simply being able to write your own sort function. Rather it’s that sorts provide readily understandable examples of entire classes of algorithms. Mergesort and quicksort are both examples of a general approach called ‘divide and conquer’. You probably will never need to re-write mergesort, but if you understand mergesort you have a much better chance of recognizing when a ‘divide and conquer’ approach can be used to solve problems you do face.
To be honest, I’ve been a software developer for more than 30 years and haven’t had to write a sort function in at least 20 years. Yes, it’s important to understand how they work, but frankly, I can’t remember the last time I actually used a sort explicitly, it’s generally implicitly done by the libraries or backend you are using.
4
Usually you don’t have to understand all aspects of the actual implementation of a specific language/library/environment. It is also not a common task to implement those manually as implementations for any environment exist.
By learning the concepts of different search algorithms is a key part of any computer science curriculum, though. By this students learn many fundamental techniques for any algorithm and algorithm comparison. One also learns different approaches which can be used for other algorithms, too.
Looking at this from a practical purpose: Sorting is a common operation. Knowing sort algorithms helps to pick the best choice at hand. Even though the Java designers have made a good choice for general purpose (I’m, not deep into Java but think they have different implementations and pick one depending on the case …) but if you know your data you probably might pick a better algorithm.
4
While I’ve never had to implement a standard sort outside of school, what does come up occasionally are situations where I need an algorithm that is just different enough that I can’t use a standard one. In those situations, I have to figure out the best standard algorithm to start with, and modify it to suit my needs.
For example, I’m currently writing a calculator as a hobby project. To handle operator precedence, I’m using the Shunting-yard algorithm, but all the implementations I could find assume that the entire expression is available when you start running the algorithm, whereas I need to be able to sort of “pause” in the middle of the algorithm while the user is still in the process of punching buttons. Not a huge deviation from the standard implementation, but different enough that I had to have a really good understanding of how and why it works.
So, don’t stress out about algorithms being difficult, but don’t blow off the lessons either. It will get easier with time.