<p>First, it is not "well accepted" that processing sorted array is more efficient. It depends on what you do. If you spend your time inserting, for instance, then sorted arrays are not necessarily a good choice. You are better off inserting at the end (say if you have resizable arrays such as <code>Vector&lt;X&gt; or ArrayList&lt;X&gt;</code> in Java), and then sort afterwards (you'll pay <span class="math-container">$O(N*log(N))$</span> instead of <span class="math-container">$O(N²)$</span>).</p>

<p>It is true that if you don't have insertions (or very few insertions with respect to searching or other operations for instance) then it is more efficient.
If you want to find an element in a sorted array, you can use binary search which is <span class="math-container">$O(log(N))$</span> while if your array is not sorted you have to scan the whole thing which is <span class="math-container">$O(N)$</span>.</p>

<p>Likewise if you want to perform set operations on two sorted arrays (intersection, union, difference), then doing so on sorted Arrays is linear. If they are not sorted you will be either quadratic (naive algorithm) or have to use an auxiliary data structure (such as a hash table).</p>

<p>Sorted arrays have the same complexity for these operations than the more involved tree structures (AVL or red-black trees) and they have a very compact and simple representation. But you pay the price that insertion is more expensive, since it has to maintain the order of elements.</p>

CC BY-SA 4.0
2018-12-03T11:32:52.757Z
Inserting in a sorted list can be done in O(n), in fact this is an example where a sorted list helps. Only Insertion Sort takes O(n²)
OBu
CC BY-SA 4.0
2018-12-03T11:50:28.440Z
That's my point. If your use case is to insert a lot of values, and have the result sorted at the end it is better to insert at the end of the array (constant time for the structures I mention) and sort everything afterwards. Other wise the whole process takes O(N²) (N is the number of elements inserted). Of course the insertion of a single element is linear. Also, OP asks specifically about arrays. In that case, insertion also needs to move the rest of the elements to the right (which is also linear). So again, it all depends on your use case.
Kim Nguyễn
CC BY-SA 4.0
2018-12-03T19:14:12.750Z
@OBu, inserting in a sorted _linked_ list can be done in O(n), but "List" does not always mean LinkedList.
Solomon Slow
CC BY-SA 4.0
2018-12-03T21:32:52.993Z
@SolomonSlow The same holds true for an array implementation.
OBu
CC BY-SA 4.0
2018-12-03T22:11:45.170Z
D'Oh! You're right!
Solomon Slow
CC BY-SA 4.0
2018-12-05T08:35:42.120Z
@OBu inserting n element in to a list $O(n^2)$. Kim is discussing inserting **lots** of elements, not just one.
ctrl-alt-delor
CC BY-SA 4.0
2018-12-05T08:37:10.773Z
While all the facts here are correct, I see nothing about a pedagogical approach.
ctrl-alt-delor
CC BY-SA 4.0
2018-12-07T00:05:40.263Z
@ctrl-alt-delor I think the approach would be: *tell them this stuff.* But I have been wrong before.
Scott Rowe
CC BY-SA 4.0
2018-12-03T06:22:47.483Z
2018-12-05T08:29:53.273Z
2018-12-05T08:29:53.273Z
Kim Nguyễn
<p>I would do it unplugged. Give then a sorted stack of cards, get them to find a number. Repeat with an unsorted list. </p>

<p>Ensure that there are gaps, <strong>not a sequence</strong>, but sorted. I got caught out with this, pupils could find a card in a sequence in <span class="math-container">$O(1)$</span>.</p>

CC BY-SA 4.0
2018-12-05T08:40:21.753Z
2018-12-05T08:40:21.753Z
ctrl-alt-delor
<p>If an array is unsorted, and you want to check an item for membership in it, that is O(n) time procedure.  If it is sorted, you can use divide-and-conquer to do this task in O(log(n) time.  </p>

CC BY-SA 4.0
2018-12-08T18:35:56.350Z
2018-12-08T18:35:56.350Z
ncmathsadist
<p>It is well accepted that processing sorted arrays is easier and efficient. What would be the pedagogical approach to explain how and why it is more efficient to process sorted collections than unsorted collections.</p>

CC BY-SA 4.0
2018-12-03T11:33:40.380Z
Hi m__, welcome to [cseducators.se]. What do you mean by "process", and what age/level are you teaching to? Without some further details, I'm afraid @KimNguyễn's response of "no it's not" is about as far as we can help you.
Ben I.
<java><c>
Why and how is it efficient to process sorted arrays than unsorted arrays?
# Why and how is it efficient to process sorted arrays than unsorted arrays?

(Asked by: username_0 on 2018-12-03)

It is well accepted that processing sorted arrays is easier and efficient. What would be the pedagogical approach to explain how and why it is more efficient to process sorted collections than unsorted collections.

**Tags:** java, c

> **Comments:**
> **username_1**: Hi m__, welcome to [cseducators.se]. What do you mean by "process", and what age/level are you teaching to? Without some further details, I'm afraid @KimNguyễn's response of "no it's not" is about as far as we can help you.  

---

## 3 answers

### Answer by username_2 on 2018-12-03. Score: 6 | Accepted answer

First, it is not "well accepted" that processing sorted array is more efficient. It depends on what you do. If you spend your time inserting, for instance, then sorted arrays are not necessarily a good choice. You are better off inserting at the end (say if you have resizable arrays such as `Vector or ArrayList` in Java), and then sort afterwards (you'll pay $O(N\*log(N))$ instead of $O(N²)$).

It is true that if you don't have insertions (or very few insertions with respect to searching or other operations for instance) then it is more efficient.
If you want to find an element in a sorted array, you can use binary search which is $O(log(N))$ while if your array is not sorted you have to scan the whole thing which is $O(N)$.

Likewise if you want to perform set operations on two sorted arrays (intersection, union, difference), then doing so on sorted Arrays is linear. If they are not sorted you will be either quadratic (naive algorithm) or have to use an auxiliary data structure (such as a hash table).

Sorted arrays have the same complexity for these operations than the more involved tree structures (AVL or red-black trees) and they have a very compact and simple representation. But you pay the price that insertion is more expensive, since it has to maintain the order of elements.

> **Comments:**
> **username_3**: Inserting in a sorted list can be done in O(n), in fact this is an example where a sorted list helps. Only Insertion Sort takes O(n²)  
> **username_2**: That's my point. If your use case is to insert a lot of values, and have the result sorted at the end it is better to insert at the end of the array (constant time for the structures I mention) and sort everything afterwards. Other wise the whole process takes O(N²) (N is the number of elements inserted). Of course the insertion of a single element is linear. Also, OP asks specifically about arrays. In that case, insertion also needs to move the rest of the elements to the right (which is also linear). So again, it all depends on your use case.  
> **username_4**: @username_3, inserting in a sorted _linked_ list can be done in O(n), but "List" does not always mean LinkedList.  
> **username_3**: @SolomonSlow The same holds true for an array implementation.  
> **username_4**: D'Oh! You're right!  
> **username_5**: @username_3 inserting n element in to a list $O(n^2)$. Kim is discussing inserting **lots** of elements, not just one.  
> **username_5**: While all the facts here are correct, I see nothing about a pedagogical approach.  
> **username_6**: @username_5 I think the approach would be: *tell them this stuff.* But I have been wrong before.  

---

### Answer by username_5 on 2018-12-05. Score: 4

I would do it unplugged. Give then a sorted stack of cards, get them to find a number. Repeat with an unsorted list.

Ensure that there are gaps, **not a sequence**, but sorted. I got caught out with this, pupils could find a card in a sequence in $O(1)$.


---

### Answer by username_7 on 2018-12-08. Score: 1

If an array is unsorted, and you want to check an item for membership in it, that is O(n) time procedure. If it is sorted, you can use divide-and-conquer to do this task in O(log(n) time.


---

