/* eslint spaced-comment: 0 */
const assert = require('chai').assert;

/// title: Bookshop in Rome
/// type: arcade-mode

/// catgories:
/// algorithms
/// sorting

/// images:
/// public/img/challenges/pexels-photo-358717.jpeg

/// description:
/// <img class='challenge__image' src='public/img/challenges/pexels-photo-358717.jpeg'>
/// On your last day of vacation, a quaint used bookstore catches your eye on one of the smaller streets of Rome. "Perhaps this bookstore will have that out of print book I have been looking for all these years." As you walk inside, you note the large pile of books in the back of the store and the sparsely-furnished bookshelves throughout. The shopkeep, a thin elderly man with combed back white hair and spectacles, seems to be deep in the process of organizing one of the bookshelves. You browse each aisle with ease due to the sparseness, but also because of your familiarity with the cover design of the book. It is then that you finally notice it on the bookshelf with other old books. "They have it!" you think estatically. Of course, you made sure multiple times.
/// As you approach the shopkeep to purchase the book, he becomes visibly startled at your presence. "Goodness! I thought I had locked the door. I apologize, but due to the recent earthquake most of the books need to be resorted before I can reopen the store."
/// Noting the book you have in your hand, he continues. "That's quite the rare book. I can offer it to you if you help me sort through all the books here. I cannot sell it for anything else at this point."
/// Understanding that your flight is tomorrow, you only have today to sort through all the books. Luckily for you, you know a few sorting algorithms. You accept the shopkeep's offer.
/// Given an array of book author last names, sort the books without using Array.prototype.sort().

/// challengeSeed:
function sortBooks (arr) {
  // Good luck!
  return true;
}

/// solutions:
function sortBooks (arr) {
  if (arr.length <= 1) {
    return arr;
  }
  // quick sort implementation
  const pivot = arr[Math.floor(arr.length / 2)]; // use approx middle element as pivot
  let leftIndex = 0;
  let rightIndex = arr.length - 1;
  while (leftIndex < rightIndex) {
    if (arr[leftIndex] >= pivot) {
      if (arr[rightIndex] <= pivot) {
        [arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], arr[leftIndex]]; // swap
        leftIndex++;
      }
      rightIndex--;
    }
    else leftIndex++;
  }

  const rightSide = arr.splice(leftIndex);
  const leftSide = arr;

  return sortBooks(leftSide).concat(sortBooks(rightSide));
}

/// tail:
const userProvidedArr = ['Rossi', 'Russo', 'Ferrarri', 'Esposito', 'Bianchi', 'Romano', 'Columbo'];
const unmodifiedArr = ['Rossi', 'Russo', 'Ferrarri', 'Esposito', 'Bianchi', 'Romano', 'Columbo'];
function isSorted (arr) {
  const check = i => (i === arr.length - 1) ? true : (arr[i] > arr[i + 1]) ? false : check(i + 1);
  return check(0);
}

/// tests:
assert(typeof sortBooks === 'function', 'message: <code>sortBooks</code> is a function.');
assert(isSorted(sortBooks(userProvidedArr)), 'message: <code>sortBooks</code> returns a sorted array.');
assert.sameMembers(sortBooks(userProvidedArr), unmodifiedArr, 'message: <code>sortBooks</code> returns an array that is unchanged except for order.');
assert.strictEqual(code.search(/\.sort\(/), -1, 'message: <code>sortBooks</code> should not use the built-in <code>.sort()</code> method.');

@@ -537,18 +537,41 @@
 se years
+,%22 you think to yourself
 .
-%22
  As you 
@@ -1032,18 +1032,19 @@
 h other 
-ol
+age
 d books.
@@ -1776,16 +1776,20 @@
  offer.%0A
+///%0A
 /// Give
@@ -2023,18 +2023,17 @@
 gth 
-%3C=
+%3E
  1) %7B%0A  
   re
@@ -2032,26 +2032,8 @@
 %7B%0A  
-  return arr;%0A  %7D%0A
   //
@@ -2059,16 +2059,18 @@
 ntation%0A
+  
   const 
@@ -2148,16 +2148,18 @@
 s pivot%0A
+  
   let le
@@ -2171,16 +2171,18 @@
 ex = 0;%0A
+  
   let ri
@@ -2208,16 +2208,18 @@
 th - 1;%0A
+  
   while 
@@ -2245,24 +2245,26 @@
 ndex) %7B%0A    
+  
 if (arr%5Bleft
@@ -2280,32 +2280,34 @@
  pivot) %7B%0A      
+ 
+ 
 if (arr%5BrightInd
@@ -2314,32 +2314,34 @@
 ex%5D %3C= pivot) %7B%0A
+  
         %5Barr%5Blef
@@ -2419,16 +2419,18 @@
         
+ 
+ 
 leftInde
@@ -2436,26 +2436,30 @@
 ex++;%0A      
-%7D%0A
+  %7D%0A  
       rightI
@@ -2466,26 +2466,30 @@
 ndex--;%0A    
-%7D%0A
+  %7D%0A  
     else lef
@@ -2502,13 +2502,17 @@
 ++;%0A
+  
   %7D%0A%0A
+  
   co
@@ -2520,20 +2520,20 @@
 st right
-Side
+Half
  = arr.s
@@ -2550,16 +2550,18 @@
 Index);%0A
+  
   const 
@@ -2564,20 +2564,20 @@
 nst left
-Side
+Half
  = arr;%0A
@@ -2579,23 +2579,45 @@
 arr;%0A%0A  
-return 
+  Array.prototype.push.apply(
 sortBook
@@ -2626,21 +2626,15 @@
 left
-Side).concat(
+Half), 
 sort
@@ -2648,14 +2648,33 @@
 ight
-Side))
+Half));%0A  %7D%0A%0A  return arr
 ;%0A%7D%0A

update algorithm and description wording