title: Sort a string based on the order of another string
body: <p>I was tasked with ordering a string based on another string assuming everything in the string is also in the sorting string</p>
  <p>E.G.</p>
  <p>s = &quot;Hello World&quot;</p>
  <p>orderString = &quot; odlehwr&quot;</p>
  <p>output: &quot; oodlllehwr&quot;</p>
  <p>I managed to do it in O(nlogn) time, but I was told after that it should be O(n + m) time and I just don't see how it's possible since it's a sort function, but I hope someone could point me in the right direction.</p>
  <p>Here's my original code:</p>
  <pre><code>std::string _sortOrder;
  std::string _input;
  
  bool customComp(char c1, char c2) {
      //checks to see which is equal first in sequential order
      for (int i = 0; i &lt; _sortOrder.length(); i++) {
          if (_sortOrder[i] == c2) {
              return false;
          }
          else if (_sortOrder[i] == c1) {
              return true;
          }
      }
  }
  
  void Question2::SortLetters(char* input, char* sortOrder) {
      //uses strings for maintainability
      _sortOrder = sortOrder;
      _input = input;
  
      //sorts using the custom comparator based on sortOrder
      std::sort(_input.begin(), _input.end(), customComp);
      std::copy(_input.begin(), _input.end(), input);
  }
  </code></pre>