Online Sorting Algorithm for fixed size array/list

Question

What would be the best way to maintain and sort a fixed-size array (or linked list?)? To make situation clear, suppose that 100 samples of data are stored in a buffer (assume they're sorted for simplicity), then when the next sample comes in, oldest one goes out and the new sample must be put in the buffer in a location such that its sorted.

What would be the best way to store these samples, arrays or linked list? And how to sort the list for the latest chunk of sample?

[Initially the buffer may be initialized to 0]

Answer 1

Both arrays and linked lists are pretty bad to keep data that must be kept sorted after each update. Either have to resort the list (O(nlogn)) after an update, or insert/remove/move the new element to its appropriate position in the sorted list (O(n)).

A better idea is to use a data structure that is inherently sorted and maintains that property after each update in O(log(n)). Both binary search trees and skip lists have that property. Many languages have a container that is implemented as a fast sorted data structure (e.g. set in C++ and TreeSet in Java).