Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-03T11:32:52.757Z
Answers.Text: 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²)
Answers.UserDisplayName: OBu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-03T11:50:28.440Z
Answers.Text: 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.
Answers.UserDisplayName: Kim Nguyễn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-03T19:14:12.750Z
Answers.Text: @OBu, inserting in a sorted _linked_ list can be done in O(n), but "List" does not always mean LinkedList.
Answers.UserDisplayName: Solomon Slow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-03T21:32:52.993Z
Answers.Text: @SolomonSlow The same holds true for an array implementation.
Answers.UserDisplayName: OBu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-03T22:11:45.170Z
Answers.Text: D'Oh! You're right!
Answers.UserDisplayName: Solomon Slow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-05T08:35:42.120Z
Answers.Text: @OBu inserting n element in to a list $O(n^2)$. Kim is discussing inserting **lots** of elements, not just one.
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-05T08:37:10.773Z
Answers.Text: While all the facts here are correct, I see nothing about a pedagogical approach.
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-07T00:05:40.263Z
Answers.Text: @ctrl-alt-delor I think the approach would be: *tell them this stuff.* But I have been wrong before.
Answers.UserDisplayName: Scott Rowe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-03T06:22:47.483Z
Answers.LastActivityDate: 2018-12-05T08:29:53.273Z
Answers.LastEditDate: 2018-12-05T08:29:53.273Z
Answers.UserDisplayName: Kim Nguyễn
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-05T08:40:21.753Z
Answers.LastActivityDate: 2018-12-05T08:40:21.753Z
Answers.UserDisplayName: ctrl-alt-delor
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-08T18:35:56.350Z
Answers.LastActivityDate: 2018-12-08T18:35:56.350Z
Answers.UserDisplayName: ncmathsadist
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-03T11:33:40.380Z
Comments.Text: 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.
Comments.UserDisplayName: Ben I.
Tags: <java><c>
Title: Why and how is it efficient to process sorted arrays than unsorted arrays?
ThreadText: # 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 @username_2'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<X> or ArrayList<X>` 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**: @username_4 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.
  
  
  ---
  
  