| Sorted array | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | Array | |||||||||||||||||||||||
| Invented | 1945 | |||||||||||||||||||||||
| Invented by | John von Neumann | |||||||||||||||||||||||
| ||||||||||||||||||||||||
Asorted array is anarray data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used incomputer science to implementstaticlookup tables to hold multiple values which have the samedata type. Sorting an array is useful in organisingdata in ordered form and recovering them rapidly.
Sorted arrays are the most space-efficient data structure with the bestlocality of reference for sequentially stored data.[citation needed]
Elements within a sorted array are found using abinary search, in O(logn); thus sorted arrays are suited for cases when one needs to be able to look up elements quickly, e.g. as aset ormultisetdata structure. This complexity for lookups is the same as forself-balancing binary search trees.
In some data structures, an array of structures is used. In such cases, the same sorting methods can be used to sort the structures according to some key as a structure element; for example, sorting records of students according to roll numbers or names or grades.
If one is using a sorteddynamic array, then it is possible to insert and delete elements. The insertion and deletion of elements in a sorted array executes at O(n), due to the need to shift all the elements following the element to be inserted or deleted; in comparison a self-balancing binary search tree inserts and deletes at O(logn). In the case where elements are deleted or inserted at the end, a sorted dynamic array can do this inamortized O(1) time while a self-balancing binary search tree always operates at O(logn).
Elements in a sorted array can be looked up by their index (random access) at O(1) time, an operation taking O(logn) or O(n) time for more complex data structures.
John von Neumann wrote the first array sorting program (merge sort) in 1945, when thefirst stored-program computer was still being built.[1][2]