Efficient sorting algorithm in terms of memory usage?

Question

So, for the project I am working so that one of the parts needs sorting. All this is done in the MIPS assembly language. I am currently discussing using either Insertion or Bubble Sort. I know that these two are slow compared to Merge and Quick sort, but I am trying to get this least amount of static / dynamic instructions. Which one would be more effective in this case? I feel that there is always a trade-off between speed and memory usage. It's true?

Answer 1

It depends a lot on the size of the arrays you want to sort. For large arrays, simple sorting algorithms, like a bubble view, tend to be very slow.

Most people do not know that due to the small size of the code, for fairly small arrays, bubble sorting can even be faster than quick sorting (and other “fast” varieties).

So:

• If your arrays are variable sizes and maximum size, if they are quite large, use quick sort (or similar), or later you should explain how the build program works so slowly. :)

• If the arrays are small enough (probably up to several hundred elements), use bubble sorting and you will have both - small code size and high performance.

• In my experience, sorting arrays is not so common. Are you really sure you need to sort these arrays?

Answer 2

My recollection of sorting an insert is that you get new records one at a time, so if you already have data to sort, you will need twice as much data — one for reading, one for writing. For any nontrivial dataset, this is likely to cost more memory than the sorting algorithm. Bubbles can be sorted in place (i.e. if you already have a block of data to sort, enough extra memory is needed to store one record or even one byte.

Sorting bubbles will also require less code to write.

Since there is always a trade-off between speed and memory (or, indeed, any two resources), this is not always the case. However, if Method A is faster and simpler and uses less memory than Method B, then B is really not suitable for competition.