Revert "[array] Move Array#sort pre-processing to Torque"

This reverts commit 2b0ac2fb9f355a7a5f2b6470c6357ebf73cfe4cc.

Reason for revert: Breaks scrollingcoordinator/non-fast-scrollable-region-nested.html layout test on https://ci.chromium.org/p/v8/builders/ci/V8-Blink%20Linux%2064/32241 

Original change's description:
> [array] Move Array#sort pre-processing to Torque
> 
> This CL removes the "PrepareElementsForSort" runtime function, and
> replaces it with a simpler version in Torque. The biggest difference
> is that certain sparse configurations no longer have a fast-path.
> 
> The Torque pre-processing step replaces the existing Torque mechanism that
> copied already pre-processed elements into the "work" FixedArray. The Torque
> compacting works as follows:
>   - Iterate all elements from 0 to {length}
>     - If the element is the hole: Do nothing.
>     - If the element is "undefined": Increment undefined counter.
>     - In all other cases, push the element into the "work" FixedArray.
> 
> Then the "work" FixedArray is sorted as before. Writing the elements from
> the "work" array back into the receiver, after sorting, has three steps:
>   1. Copy the sorted elements from the "work" FixedArray to the receiver.
>   2. Add previously counted number of "undefined" to the receiver.
>   3. Depending on the backing store either delete properties or
>      set them to the Hole up to {length}.
> 
> Bug: v8:8714
> Change-Id: I14eccb7cfd2e4618bce2a85cba0689d7e0380ad2
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1619756
> Commit-Queue: Simon Zünd <szuend@chromium.org>
> Reviewed-by: Tobias Tebbi <tebbi@chromium.org>
> Reviewed-by: Jakob Gruber <jgruber@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#61812}

TBR=peter.wm.wong@gmail.com,jgruber@chromium.org,tebbi@chromium.org,szuend@chromium.org

Change-Id: If1c1bc07f38dfbd4bf6b6ce8f9d70714e7526877
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: v8:8714
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1627976
Reviewed-by: Simon Zünd <szuend@chromium.org>
Commit-Queue: Simon Zünd <szuend@chromium.org>
Cr-Commit-Position: refs/heads/master@{#61814}
diff --git a/src/builtins/base.tq b/src/builtins/base.tq
index 898bffb..cdfb23f 100644
--- a/src/builtins/base.tq
+++ b/src/builtins/base.tq
@@ -1024,7 +1024,6 @@
     constexpr int31 generates 'V8_TYPED_ARRAY_MAX_SIZE_IN_HEAP';
 const kMaxSafeInteger: constexpr float64 generates 'kMaxSafeInteger';
 const kSmiMaxValue: constexpr uintptr generates 'kSmiMaxValue';
-const kSmiMax: uintptr = kSmiMaxValue;
 const kStringMaxLength: constexpr int31 generates 'String::kMaxLength';
 const kFixedArrayMaxLength:
     constexpr int31 generates 'FixedArray::kMaxLength';
diff --git a/src/debug/debug-evaluate.cc b/src/debug/debug-evaluate.cc
index a4960cd..3f7e4f68 100644
--- a/src/debug/debug-evaluate.cc
+++ b/src/debug/debug-evaluate.cc
@@ -263,6 +263,7 @@
   V(HasFastPackedElements)                    \
   V(NewArray)                                 \
   V(NormalizeElements)                        \
+  V(PrepareElementsForSort)                   \
   V(TypedArrayGetBuffer)                      \
   /* Errors */                                \
   V(NewTypeError)                             \
@@ -512,6 +513,7 @@
     case Builtins::kArrayPrototypeKeys:
     case Builtins::kArrayPrototypeLastIndexOf:
     case Builtins::kArrayPrototypeSlice:
+    case Builtins::kArrayPrototypeSort:
     case Builtins::kArrayPrototypeToLocaleString:
     case Builtins::kArrayPrototypeToString:
     case Builtins::kArrayForEach:
@@ -785,7 +787,6 @@
     case Builtins::kArrayPrototypeReverse:
     case Builtins::kArrayPrototypeShift:
     case Builtins::kArrayPrototypeUnshift:
-    case Builtins::kArrayPrototypeSort:
     case Builtins::kArrayPrototypeSplice:
     case Builtins::kArrayUnshift:
     // Map builtins.
diff --git a/src/objects/fixed-array.h b/src/objects/fixed-array.h
index 5896f41..0216767 100644
--- a/src/objects/fixed-array.h
+++ b/src/objects/fixed-array.h
@@ -140,6 +140,8 @@
 
   inline ObjectSlot GetFirstElementAddress();
   inline bool ContainsOnlySmisOrHoles();
+  // Returns true iff the elements are Numbers and sorted ascending.
+  bool ContainsSortedNumbers();
 
   // Gives access to raw memory which stores the array's data.
   inline ObjectSlot data_start();
diff --git a/src/objects/js-objects.cc b/src/objects/js-objects.cc
index 3fe98c9..2f7e179 100644
--- a/src/objects/js-objects.cc
+++ b/src/objects/js-objects.cc
@@ -1963,6 +1963,17 @@
                                try_fast_path, true);
 }
 
+Handle<FixedArray> JSReceiver::GetOwnElementIndices(Isolate* isolate,
+                                                    Handle<JSReceiver> receiver,
+                                                    Handle<JSObject> object) {
+  KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly,
+                             ALL_PROPERTIES);
+  accumulator.CollectOwnElementIndices(receiver, object);
+  Handle<FixedArray> keys =
+      accumulator.GetKeys(GetKeysConversion::kKeepNumbers);
+  DCHECK(keys->ContainsSortedNumbers());
+  return keys;
+}
 Maybe<bool> JSReceiver::SetPrototype(Handle<JSReceiver> object,
                                      Handle<Object> value, bool from_javascript,
                                      ShouldThrow should_throw) {
diff --git a/src/objects/js-objects.h b/src/objects/js-objects.h
index b9a7014..361c74b 100644
--- a/src/objects/js-objects.h
+++ b/src/objects/js-objects.h
@@ -259,6 +259,9 @@
       Handle<JSReceiver> object, PropertyFilter filter,
       bool try_fast_path = true);
 
+  V8_WARN_UNUSED_RESULT static Handle<FixedArray> GetOwnElementIndices(
+      Isolate* isolate, Handle<JSReceiver> receiver, Handle<JSObject> object);
+
   static const int kHashMask = PropertyArray::HashField::kMask;
 
   DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize,
diff --git a/src/objects/objects.cc b/src/objects/objects.cc
index fece0b5..5969435 100644
--- a/src/objects/objects.cc
+++ b/src/objects/objects.cc
@@ -3811,6 +3811,20 @@
   return new_array;
 }
 
+bool FixedArray::ContainsSortedNumbers() {
+  for (int i = 1; i < length(); ++i) {
+    Object a_obj = get(i - 1);
+    Object b_obj = get(i);
+    if (!a_obj.IsNumber() || !b_obj.IsNumber()) return false;
+
+    uint32_t a = NumberToUint32(a_obj);
+    uint32_t b = NumberToUint32(b_obj);
+
+    if (a > b) return false;
+  }
+  return true;
+}
+
 Handle<FixedArray> FixedArray::ShrinkOrEmpty(Isolate* isolate,
                                              Handle<FixedArray> array,
                                              int new_length) {
diff --git a/src/runtime/runtime-array.cc b/src/runtime/runtime-array.cc
index ef5275d..a7d10c7 100644
--- a/src/runtime/runtime-array.cc
+++ b/src/runtime/runtime-array.cc
@@ -15,6 +15,7 @@
 #include "src/objects/elements.h"
 #include "src/objects/hash-table-inl.h"
 #include "src/objects/js-array-inl.h"
+#include "src/objects/keys.h"
 #include "src/objects/prototype.h"
 #include "src/runtime/runtime-utils.h"
 
@@ -41,6 +42,386 @@
   return *object;
 }
 
+namespace {
+// Find the next free position. undefined and holes are both considered
+// free spots. Returns "Nothing" if an exception occurred.
+V8_WARN_UNUSED_RESULT
+Maybe<uint32_t> FindNextFreePosition(Isolate* isolate,
+                                     Handle<JSReceiver> receiver,
+                                     uint32_t current_pos) {
+  for (uint32_t position = current_pos;; ++position) {
+    Maybe<bool> has_element = JSReceiver::HasOwnProperty(receiver, position);
+    MAYBE_RETURN(has_element, Nothing<uint32_t>());
+    if (!has_element.FromJust()) return Just(position);
+
+    Handle<Object> element;
+    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+        isolate, element, JSReceiver::GetElement(isolate, receiver, position),
+        Nothing<uint32_t>());
+    if (element->IsUndefined(isolate)) return Just(position);
+  }
+}
+
+// As RemoveArrayHoles, but also handles Dictionary elements that stay
+// Dictionary (requires_slow_elements() is true), proxies and objects that
+// might have accessors.
+V8_WARN_UNUSED_RESULT
+Object RemoveArrayHolesGeneric(Isolate* isolate, Handle<JSReceiver> receiver,
+                               uint32_t limit) {
+  HandleScope scope(isolate);
+
+  // For proxies, we do not collect the keys, instead we use all indices in
+  // the full range of [0, limit).
+  Handle<FixedArray> keys;
+  if (!receiver->IsJSProxy()) {
+    keys = JSReceiver::GetOwnElementIndices(isolate, receiver,
+                                            Handle<JSObject>::cast(receiver));
+  }
+
+  uint32_t num_undefined = 0;
+  uint32_t current_pos = 0;
+  uint32_t num_indices = keys.is_null() ? limit : keys->length();
+
+  // Compact keys with undefined values and moves non-undefined
+  // values to the front.
+  // The loop does two things simultaneously:
+  //   (1) Count the number of 'undefined', i.e.
+  //       i.e.: HasProperty(receiver, key) && Get(receiver, key) == undefined
+  //   (2) Move all non-undefined values to the front. The variable current_pos
+  //       is used to track free spots in the array starting at the beginning.
+  //       Holes and 'undefined' are considered free spots.
+  //       A hole is when HasElement(receiver, key) is false.
+  for (uint32_t i = 0; i < num_indices; ++i) {
+    uint32_t key = keys.is_null() ? i : NumberToUint32(keys->get(i));
+
+    // We only care about array indices that are smaller than the limit.
+    // The keys are sorted, so we can break as soon as we encounter the first.
+    if (key >= limit) break;
+
+    Maybe<bool> has_element = JSReceiver::HasElement(receiver, key);
+    MAYBE_RETURN(has_element, ReadOnlyRoots(isolate).exception());
+    if (!has_element.FromJust()) {
+      continue;
+    }
+
+    Handle<Object> element;
+    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+        isolate, element, JSReceiver::GetElement(isolate, receiver, key));
+
+    if (element->IsUndefined(isolate)) {
+      ++num_undefined;
+    } else {
+      // Find next free position to move elements to.
+      Maybe<uint32_t> free_position =
+          FindNextFreePosition(isolate, receiver, current_pos);
+      MAYBE_RETURN(free_position, ReadOnlyRoots(isolate).exception());
+      current_pos = free_position.FromJust();
+
+      // Do not move elements that are already in the "packed" area.
+      if (key <= current_pos) continue;
+
+      // array[current_pos] = array[key].
+      // Deleting array[key] is done later. This is to preserve the same
+      // semantics as the old JS implementation when working with non-extensible
+      // objects:
+      // If the array contains undefineds, the position at 'key' might later
+      // bet set to 'undefined'. If we delete the element now and later set it
+      // to undefined, the set operation would throw an exception.
+      // Instead, to mark it up as a free space, we set array[key] to undefined.
+      // As 'key' will be incremented afterward, this undefined value will not
+      // affect 'num_undefined', and the logic afterwards will correctly set
+      // the remaining undefineds or delete the remaining properties.
+      RETURN_FAILURE_ON_EXCEPTION(
+          isolate, Object::SetElement(isolate, receiver, current_pos, element,
+                                      ShouldThrow::kThrowOnError));
+      RETURN_FAILURE_ON_EXCEPTION(
+          isolate, Object::SetElement(isolate, receiver, key,
+                                      isolate->factory()->undefined_value(),
+                                      ShouldThrow::kThrowOnError));
+      ++current_pos;
+    }
+  }
+
+  // current_pos points to the next free space in the array/object. In most
+  // cases this corresponds to the 'length' or to the number of non-undefined
+  // elements.
+  // In cases where an object is 'packed' and 'length' is smaller, e.g.:
+  //      { 0: 5, 1: 4, 2: 3, length: 2 }
+  // current_pos will be greater than limit, thus, we need to take the minimum.
+  uint32_t result = std::min(current_pos, limit);
+
+  // Set [current_pos, current_pos + num_undefined) to undefined.
+  for (uint32_t i = 0; i < num_undefined; ++i) {
+    RETURN_FAILURE_ON_EXCEPTION(
+        isolate, Object::SetElement(isolate, receiver, current_pos++,
+                                    isolate->factory()->undefined_value(),
+                                    ShouldThrow::kThrowOnError));
+  }
+  // TODO(szuend): Re-enable when we also copy from the prototype chain for
+  //               JSArrays. Then we can use HasOwnProperty instead of
+  //               HasElement and this condition will hold.
+  // DCHECK_LE(current_pos, num_indices);
+
+  // Deleting everything after the undefineds up unto the limit.
+  for (uint32_t i = num_indices; i > 0;) {
+    --i;
+    uint32_t key = keys.is_null() ? i : NumberToUint32(keys->get(i));
+    if (key < current_pos) break;
+    if (key >= limit) continue;
+
+    Maybe<bool> delete_result = JSReceiver::DeleteElement(receiver, key);
+    MAYBE_RETURN(delete_result, ReadOnlyRoots(isolate).exception());
+  }
+
+  return *isolate->factory()->NewNumberFromUint(result);
+}
+
+// Collects all defined (non-hole) and non-undefined (array) elements at the
+// start of the elements array.  If the object is in dictionary mode, it is
+// converted to fast elements mode.  Undefined values are placed after
+// non-undefined values.  Returns the number of non-undefined values.
+V8_WARN_UNUSED_RESULT
+Object RemoveArrayHoles(Isolate* isolate, Handle<JSReceiver> receiver,
+                        uint32_t limit) {
+  if (receiver->IsJSProxy()) {
+    return RemoveArrayHolesGeneric(isolate, receiver, limit);
+  }
+
+  Handle<JSObject> object = Handle<JSObject>::cast(receiver);
+  if (object->HasStringWrapperElements()) {
+    int len = String::cast(Handle<JSValue>::cast(object)->value()).length();
+    DCHECK_LE(len, limit);
+    return Smi::FromInt(len);
+  }
+
+  if (object->HasSloppyArgumentsElements() || !object->map().is_extensible()) {
+    return RemoveArrayHolesGeneric(isolate, receiver, limit);
+  }
+
+  JSObject::ValidateElements(*object);
+  if (object->HasDictionaryElements()) {
+    // Convert to fast elements containing only the existing properties.
+    // Ordering is irrelevant, since we are going to sort anyway.
+    Handle<NumberDictionary> dict(object->element_dictionary(), isolate);
+    if (object->IsJSArray() || dict->requires_slow_elements() ||
+        dict->max_number_key() >= limit) {
+      return RemoveArrayHolesGeneric(isolate, receiver, limit);
+    }
+    // Convert to fast elements.
+    Handle<Map> new_map =
+        JSObject::GetElementsTransitionMap(object, HOLEY_ELEMENTS);
+
+    AllocationType allocation = ObjectInYoungGeneration(*object)
+                                    ? AllocationType::kYoung
+                                    : AllocationType::kOld;
+    Handle<FixedArray> fast_elements =
+        isolate->factory()->NewFixedArray(dict->NumberOfElements(), allocation);
+    dict->CopyValuesTo(*fast_elements);
+
+    JSObject::SetMapAndElements(object, new_map, fast_elements);
+    JSObject::ValidateElements(*object);
+  } else if (object->HasFixedTypedArrayElements()) {
+    // Typed arrays cannot have holes or undefined elements.
+    // TODO(bmeurer, v8:4153): Change this to size_t later.
+    uint32_t array_length =
+        static_cast<uint32_t>(Handle<JSTypedArray>::cast(receiver)->length());
+    return Smi::FromInt(Min(limit, array_length));
+  } else if (!object->HasDoubleElements()) {
+    JSObject::EnsureWritableFastElements(object);
+  }
+  DCHECK(object->HasSmiOrObjectElements() || object->HasDoubleElements());
+
+  // Collect holes at the end, undefined before that and the rest at the
+  // start, and return the number of non-hole, non-undefined values.
+
+  Handle<FixedArrayBase> elements_base(object->elements(), isolate);
+  uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
+  if (limit > elements_length) {
+    limit = elements_length;
+  }
+  if (limit == 0) {
+    return Smi::kZero;
+  }
+
+  uint32_t result = 0;
+  if (elements_base->map() == ReadOnlyRoots(isolate).fixed_double_array_map()) {
+    FixedDoubleArray elements = FixedDoubleArray::cast(*elements_base);
+    // Split elements into defined and the_hole, in that order.
+    unsigned int holes = limit;
+    // Assume most arrays contain no holes and undefined values, so minimize the
+    // number of stores of non-undefined, non-the-hole values.
+    for (unsigned int i = 0; i < holes; i++) {
+      if (elements.is_the_hole(i)) {
+        holes--;
+      } else {
+        continue;
+      }
+      // Position i needs to be filled.
+      while (holes > i) {
+        if (elements.is_the_hole(holes)) {
+          holes--;
+        } else {
+          elements.set(i, elements.get_scalar(holes));
+          break;
+        }
+      }
+    }
+    result = holes;
+    while (holes < limit) {
+      elements.set_the_hole(holes);
+      holes++;
+    }
+  } else {
+    FixedArray elements = FixedArray::cast(*elements_base);
+    DisallowHeapAllocation no_gc;
+
+    // Split elements into defined, undefined and the_hole, in that order.  Only
+    // count locations for undefined and the hole, and fill them afterwards.
+    WriteBarrierMode write_barrier = elements.GetWriteBarrierMode(no_gc);
+    unsigned int undefs = limit;
+    unsigned int holes = limit;
+    // Assume most arrays contain no holes and undefined values, so minimize the
+    // number of stores of non-undefined, non-the-hole values.
+    for (unsigned int i = 0; i < undefs; i++) {
+      Object current = elements.get(i);
+      if (current.IsTheHole(isolate)) {
+        holes--;
+        undefs--;
+      } else if (current.IsUndefined(isolate)) {
+        undefs--;
+      } else {
+        continue;
+      }
+      // Position i needs to be filled.
+      while (undefs > i) {
+        current = elements.get(undefs);
+        if (current.IsTheHole(isolate)) {
+          holes--;
+          undefs--;
+        } else if (current.IsUndefined(isolate)) {
+          undefs--;
+        } else {
+          elements.set(i, current, write_barrier);
+          break;
+        }
+      }
+    }
+    result = undefs;
+    while (undefs < holes) {
+      elements.set_undefined(isolate, undefs);
+      undefs++;
+    }
+    while (holes < limit) {
+      elements.set_the_hole(isolate, holes);
+      holes++;
+    }
+  }
+
+  DCHECK_LE(result, limit);
+  return *isolate->factory()->NewNumberFromUint(result);
+}
+
+// Copy element at index from source to target only if target does not have the
+// element on its own. Returns true if a copy occurred, false if not
+// and Nothing if an exception occurred.
+V8_WARN_UNUSED_RESULT
+Maybe<bool> ConditionalCopy(Isolate* isolate, Handle<JSReceiver> source,
+                            Handle<JSReceiver> target, uint32_t index) {
+  Maybe<bool> source_has_prop = JSReceiver::HasOwnProperty(source, index);
+  MAYBE_RETURN(source_has_prop, Nothing<bool>());
+  if (!source_has_prop.FromJust()) return Just(false);
+
+  Maybe<bool> target_has_prop = JSReceiver::HasOwnProperty(target, index);
+  MAYBE_RETURN(target_has_prop, Nothing<bool>());
+  if (target_has_prop.FromJust()) return Just(false);
+
+  Handle<Object> source_element;
+  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+      isolate, source_element, JSReceiver::GetElement(isolate, target, index),
+      Nothing<bool>());
+
+  Handle<Object> set_result;
+  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+      isolate, set_result,
+      Object::SetElement(isolate, target, index, source_element,
+                         ShouldThrow::kThrowOnError),
+      Nothing<bool>());
+
+  return Just(true);
+}
+
+// Copy elements in the range 0..length from objects prototype chain
+// to object itself, if object has holes. Returns null on error and undefined on
+// success.
+V8_WARN_UNUSED_RESULT
+MaybeHandle<Object> CopyFromPrototype(Isolate* isolate,
+                                      Handle<JSReceiver> object,
+                                      uint32_t length) {
+  for (PrototypeIterator iter(isolate, object, kStartAtPrototype);
+       !iter.IsAtEnd(); iter.Advance()) {
+    Handle<JSReceiver> current(PrototypeIterator::GetCurrent<JSReceiver>(iter));
+
+    if (current->IsJSProxy()) {
+      for (uint32_t i = 0; i < length; ++i) {
+        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, i));
+      }
+    } else {
+      Handle<FixedArray> keys = JSReceiver::GetOwnElementIndices(
+          isolate, object, Handle<JSObject>::cast(current));
+
+      uint32_t num_indices = keys->length();
+      for (uint32_t i = 0; i < num_indices; ++i) {
+        uint32_t idx = NumberToUint32(keys->get(i));
+
+        // Prototype might have indices that go past length, but we are only
+        // interested in the range [0, length).
+        if (idx >= length) break;
+
+        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, idx));
+      }
+    }
+  }
+  return isolate->factory()->undefined_value();
+}
+
+}  // namespace
+
+RUNTIME_FUNCTION(Runtime_PrepareElementsForSort) {
+  HandleScope scope(isolate);
+  DCHECK_EQ(2, args.length());
+  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, object, 0);
+  CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
+
+  if (isolate->debug_execution_mode() == DebugInfo::kSideEffects) {
+    if (!isolate->debug()->PerformSideEffectCheckForObject(object)) {
+      return ReadOnlyRoots(isolate).exception();
+    }
+  }
+
+  // Counter for sorting arrays that have non-packed elements and where either
+  // the ElementsProtector is invalid or the prototype does not match
+  // Array.prototype.
+  JSObject initial_array_proto = JSObject::cast(
+      isolate->native_context()->get(Context::INITIAL_ARRAY_PROTOTYPE_INDEX));
+  if (object->IsJSArray() &&
+      !Handle<JSArray>::cast(object)->HasFastPackedElements()) {
+    if (!isolate->IsNoElementsProtectorIntact() ||
+        object->map().prototype() != initial_array_proto) {
+      isolate->CountUsage(
+          v8::Isolate::kArrayPrototypeSortJSArrayModifiedPrototype);
+    }
+  }
+
+  // Skip copying from prototype for JSArrays with ElementsProtector intact and
+  // the original array prototype.
+  if (!object->IsJSArray() || !isolate->IsNoElementsProtectorIntact() ||
+      object->map().prototype() != initial_array_proto) {
+    RETURN_FAILURE_ON_EXCEPTION(isolate,
+                                CopyFromPrototype(isolate, object, length));
+  }
+  return RemoveArrayHoles(isolate, object, length);
+}
+
 RUNTIME_FUNCTION(Runtime_NewArray) {
   HandleScope scope(isolate);
   DCHECK_LE(3, args.length());
diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h
index 2f343bf..983b64b 100644
--- a/src/runtime/runtime.h
+++ b/src/runtime/runtime.h
@@ -46,6 +46,7 @@
   I(IsArray, 1, 1)                        \
   F(NewArray, -1 /* >= 3 */, 1)           \
   F(NormalizeElements, 1, 1)              \
+  F(PrepareElementsForSort, 2, 1)         \
   F(TransitionElementsKind, 2, 1)         \
   F(TransitionElementsKindWithKind, 2, 1) \
 
diff --git a/test/js-perf-test/ArraySort/sort-base.js b/test/js-perf-test/ArraySort/sort-base.js
index 776d45e..c888972 100644
--- a/test/js-perf-test/ArraySort/sort-base.js
+++ b/test/js-perf-test/ArraySort/sort-base.js
@@ -93,9 +93,7 @@
 
 function CreateDictionaryArray() {
   array_to_sort = Array.from(template_array);
-  Object.defineProperty(array_to_sort, kArraySize - 2,
-    { get: () => this.foo,
-      set: (v) => this.foo = v });
+  array_to_sort[%MaxSmi()] = 42;
 
   AssertDictionaryElements();
 }
diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js
index 6db8759..ca0daad 100644
--- a/test/mjsunit/array-sort.js
+++ b/test/mjsunit/array-sort.js
@@ -127,8 +127,9 @@
   assertFalse(4 in obj, "objsort non-existing retained");
 }
 
-TestSparseNonArraySorting(1000);
 TestSparseNonArraySorting(5000);
+TestSparseNonArraySorting(500000);
+TestSparseNonArraySorting(Math.pow(2, 31) + 1);
 
 
 function TestArrayLongerLength(length) {
@@ -146,7 +147,8 @@
 TestArrayLongerLength(4);
 TestArrayLongerLength(10);
 TestArrayLongerLength(1000);
-TestArrayLongerLength(5000);
+TestArrayLongerLength(500000);
+TestArrayLongerLength(Math.pow(2,32) - 1);
 
 
 function TestNonArrayLongerLength(length) {
@@ -164,7 +166,8 @@
 TestNonArrayLongerLength(4);
 TestNonArrayLongerLength(10);
 TestNonArrayLongerLength(1000);
-TestNonArrayLongerLength(5000);
+TestNonArrayLongerLength(500000);
+TestNonArrayLongerLength(Math.pow(2,32) - 1);
 
 
 function TestNonArrayWithAccessors() {
diff --git a/test/mjsunit/regress/regress-v8-7682.js b/test/mjsunit/regress/regress-v8-7682.js
index 68f9e0b..86f12f5 100644
--- a/test/mjsunit/regress/regress-v8-7682.js
+++ b/test/mjsunit/regress/regress-v8-7682.js
@@ -22,5 +22,5 @@
 // the spec:
 //   - "xs" is sparse and IsExtensible(xs) is false (its frozen).
 //   - "xs" is sparse and the prototype has properties in the sort range.
-assertEquals(1, xs[0]);
-assertEquals(2, xs[1]);
+assertEquals(2, xs[0]);
+assertEquals(1, xs[1]);
diff --git a/test/mjsunit/ubsan-fuzzerbugs.js b/test/mjsunit/ubsan-fuzzerbugs.js
index ae590b6..5a7594d 100644
--- a/test/mjsunit/ubsan-fuzzerbugs.js
+++ b/test/mjsunit/ubsan-fuzzerbugs.js
@@ -72,3 +72,21 @@
   %OptimizeFunctionOnNextCall(f);
   f();
 })();
+
+// crbug.com/935133
+(function() {
+  var called_has = false;
+  var proxy = new Proxy({}, {
+    has: function(x, p) {
+      called_has = true;
+      throw "The test may finish now";
+    },
+  });
+  proxy.length = 2147483648;
+  try {
+    Array.prototype.sort.call(proxy);
+  } catch(e) {
+    assertTrue(e === "The test may finish now");
+  }
+  assertTrue(called_has);
+})();
diff --git a/test/mozilla/mozilla.status b/test/mozilla/mozilla.status
index 216d962..be0180f 100644
--- a/test/mozilla/mozilla.status
+++ b/test/mozilla/mozilla.status
@@ -163,13 +163,6 @@
   # https://crbug.com/v8/8120
   'ecma_3/Array/regress-322135-04': [SKIP],
 
-  # These tests try to sort very large arrays. Array#sort pre-processing does
-  # not support huge sparse Arrays, so these tests run a very long time.
-  # https://crbug.com/v8/8714
-  'js1_5/Array/regress-330812': [SKIP],
-  'js1_5/Regress/regress-422348': [SKIP],
-  'js1_5/Array/regress-157652': [SKIP],
-
   ##################### SLOW TESTS #####################
 
   # Compiles a long chain of && or || operations, can time out under slower
@@ -516,6 +509,7 @@
   'ecma_3/extensions/regress-274152': [FAIL_OK],
   'js1_5/Regress/regress-372364': [FAIL_OK],
   'js1_5/Regress/regress-420919': [FAIL_OK],
+  'js1_5/Regress/regress-422348': [FAIL_OK],
   'js1_5/Regress/regress-410852': [FAIL_OK],
   'ecma_3/RegExp/regress-375715-04': [FAIL_OK],
   'js1_5/decompilation/regress-456964-01': [FAIL_OK],
diff --git a/test/webkit/webkit.status b/test/webkit/webkit.status
index 014155e..c15c3b6 100644
--- a/test/webkit/webkit.status
+++ b/test/webkit/webkit.status
@@ -36,11 +36,6 @@
   # Irregexp interpreter overflows stack. We should just not crash.
   'fast/js/regexp-stack-overflow': [PASS, FAIL],
 
-  # This test tries to sort very large array. Array#sort pre-processing does
-  # not support huge sparse Arrays, so this test runs a very long time.
-  # https://crbug.com/v8/8714
-  'array-sort-small-sparse-array-with-large-length': [SKIP],
-
   # Slow tests.
   'dfg-double-vote-fuzz': [PASS, SLOW],
 }],  # ALWAYS
diff --git a/third_party/v8/builtins/array-sort.tq b/third_party/v8/builtins/array-sort.tq
index 8643348..ddd796b 100644
--- a/third_party/v8/builtins/array-sort.tq
+++ b/third_party/v8/builtins/array-sort.tq
@@ -34,7 +34,7 @@
     ResetToGenericAccessor() {
       this.loadFn = Load<GenericElementsAccessor>;
       this.storeFn = Store<GenericElementsAccessor>;
-      this.deleteFn = Delete<GenericElementsAccessor>;
+      this.bailoutStatus = kSuccess;
     }
 
     // The receiver of the Array.p.sort call.
@@ -54,14 +54,17 @@
     // uses ToString and a lexicographical compare.
     sortComparePtr: CompareBuiltinFn;
 
-    // The following four function pointer represent a Accessor/Path.
-    // These are used to Load/Store/Delete elements and to check whether
-    // to bail to the baseline GenericElementsAccessor.
+    // The following three function pointer represent a Accessor/Path.
+    // These are used to Load/Store elements and to check whether to bail to the
+    // baseline GenericElementsAccessor.
     loadFn: LoadFn;
     storeFn: StoreFn;
-    deleteFn: DeleteFn;
     canUseSameAccessorFn: CanUseSameAccessorFn;
 
+    // If this field has the value kFailure, we need to bail to the baseline
+    // GenericElementsAccessor.
+    bailoutStatus: Smi;
+
     // This controls when we get *into* galloping mode. It's initialized to
     // kMinGallop. mergeLow and mergeHigh tend to nudge it higher for random
     // data, and lower for highly structured data.
@@ -87,76 +90,48 @@
 
     // Pointer to the temporary array.
     tempArray: FixedArray;
-
-    // The initialReceiverLength converted and clamped to Smi.
-    sortLength: Smi;
-
-    // The number of undefined that need to be inserted after sorting
-    // when the elements are copied back from the workArray to the receiver.
-    numberOfUndefined: Smi;
   }
 
-  type FastSmiElements;
-  type FastObjectElements;
-
   transitioning macro NewSortState(implicit context: Context)(
       receiver: JSReceiver, comparefn: Undefined | Callable,
-      initialReceiverLength: Number): SortState {
+      initialReceiverLength: Number, sortLength: Smi,
+      forceGeneric: constexpr bool): SortState {
     const sortComparePtr =
         comparefn != Undefined ? SortCompareUserFn : SortCompareDefault;
     const map = receiver.map;
-    let loadFn: LoadFn;
-    let storeFn: StoreFn;
-    let deleteFn: DeleteFn;
-    let canUseSameAccessorFn: CanUseSameAccessorFn;
+    let loadFn = Load<GenericElementsAccessor>;
+    let storeFn = Store<GenericElementsAccessor>;
+    let canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>;
 
     try {
-      GotoIfForceSlowPath() otherwise Slow;
-      let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;
+      if constexpr (!forceGeneric) {
+        GotoIfForceSlowPath() otherwise Slow;
+        let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;
 
-      const elementsKind: ElementsKind = map.elements_kind;
-      if (IsDoubleElementsKind(elementsKind)) {
-        loadFn = Load<FastDoubleElements>;
-        storeFn = Store<FastDoubleElements>;
-        deleteFn = Delete<FastDoubleElements>;
-        canUseSameAccessorFn = CanUseSameAccessor<FastDoubleElements>;
-      } else if (IsFastSmiElementsKind(elementsKind)) {
-        loadFn = Load<FastSmiElements>;
-        storeFn = Store<FastSmiElements>;
-        deleteFn = Delete<FastSmiElements>;
-        canUseSameAccessorFn = CanUseSameAccessor<FastSmiElements>;
-      } else {
-        loadFn = Load<FastObjectElements>;
-        storeFn = Store<FastObjectElements>;
-        deleteFn = Delete<FastObjectElements>;
-        canUseSameAccessorFn = CanUseSameAccessor<FastObjectElements>;
+        const elementsKind: ElementsKind = map.elements_kind;
+        if (IsDoubleElementsKind(elementsKind)) {
+          loadFn = Load<FastDoubleElements>;
+          storeFn = Store<FastDoubleElements>;
+          canUseSameAccessorFn = CanUseSameAccessor<FastDoubleElements>;
+        } else if (elementsKind == PACKED_SMI_ELEMENTS) {
+          loadFn = Load<FastPackedSmiElements>;
+          storeFn = Store<FastPackedSmiElements>;
+          canUseSameAccessorFn = CanUseSameAccessor<FastPackedSmiElements>;
+        } else {
+          loadFn = Load<FastSmiOrObjectElements>;
+          storeFn = Store<FastSmiOrObjectElements>;
+          canUseSameAccessorFn = CanUseSameAccessor<FastSmiOrObjectElements>;
+        }
       }
     }
     label Slow {
-      loadFn = Load<GenericElementsAccessor>;
-      storeFn = Store<GenericElementsAccessor>;
-      deleteFn = Delete<GenericElementsAccessor>;
-      canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>;
-    }
-
-    // With the pre-processing step in Torque, the exact number of elements
-    // to sort is unknown at this time. The 'length' property is an upper bound
-    // (as per spec) while the actual size of the backing store is a good guess.
-    // After the pre-processing step, the workarray won't change in length.
-    let workArrayLength: intptr =
-        Signed(Convert<uintptr>(initialReceiverLength));
-    try {
-      const object = Cast<JSObject>(receiver) otherwise NoJsObject;
-      const elementsLength = Convert<intptr>(object.elements.length);
-
-      // In some cases, elements are only on prototypes, but not on the receiver
-      // itself. Do nothing then, as {workArrayLength} got initialized with the
-      // {length} property.
-      if (elementsLength != 0) {
-        workArrayLength = IntPtrMin(workArrayLength, elementsLength);
+      if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
+          !IsCustomElementsReceiverInstanceType(map.instance_type)) {
+        loadFn = Load<DictionaryElements>;
+        storeFn = Store<DictionaryElements>;
+        canUseSameAccessorFn = CanUseSameAccessor<DictionaryElements>;
       }
     }
-    label NoJsObject {}
 
     return new SortState{
       receiver,
@@ -166,18 +141,17 @@
       sortComparePtr,
       loadFn,
       storeFn,
-      deleteFn,
       canUseSameAccessorFn,
+      bailoutStatus: kSuccess,
       minGallop: kMinGallopWins,
       pendingRunsSize: 0,
       pendingRuns: AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending)),
-      workArray: AllocateZeroedFixedArray(workArrayLength),
-      tempArray: kEmptyFixedArray,
-      sortLength: 0,
-      numberOfUndefined: 0
+      workArray: AllocateZeroedFixedArray(Convert<intptr>(sortLength)),
+      tempArray: kEmptyFixedArray
     };
   }
 
+  const kFailure: Smi = -1;
   const kSuccess: Smi = 0;
 
   // The maximum number of entries in a SortState's pending-runs stack.
@@ -197,7 +171,6 @@
 
   type LoadFn = builtin(Context, SortState, Smi) => Object;
   type StoreFn = builtin(Context, SortState, Smi, Object) => Smi;
-  type DeleteFn = builtin(Context, SortState, Smi) => Smi;
   type CanUseSameAccessorFn = builtin(Context, JSReceiver, Object, Number) =>
       Boolean;
   type CompareBuiltinFn = builtin(Context, Object, Object, Object) => Number;
@@ -210,23 +183,28 @@
 
   transitioning builtin Load<ElementsAccessor: type>(
       context: Context, sortState: SortState, index: Smi): Object {
-    const receiver = sortState.receiver;
-    if (!HasProperty_Inline(receiver, index)) return Hole;
-    return GetProperty(receiver, index);
+    return GetProperty(sortState.receiver, index);
   }
 
-  Load<FastSmiElements>(context: Context, sortState: SortState, index: Smi):
-      Object {
+  Load<FastPackedSmiElements>(
+      context: Context, sortState: SortState, index: Smi): Object {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
     return elements.objects[index];
   }
 
-  Load<FastObjectElements>(context: Context, sortState: SortState, index: Smi):
-      Object {
+  Load<FastSmiOrObjectElements>(
+      context: Context, sortState: SortState, index: Smi): Object {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
-    return elements.objects[index];
+    const result: Object = elements.objects[index];
+    if (IsTheHole(result)) {
+      // The pre-processing step removed all holes by compacting all elements
+      // at the start of the array. Finding a hole means the cmp function or
+      // ToString changes the array.
+      return Failure(sortState);
+    }
+    return result;
   }
 
   Load<FastDoubleElements>(context: Context, sortState: SortState, index: Smi):
@@ -234,11 +212,28 @@
     try {
       const object = UnsafeCast<JSObject>(sortState.receiver);
       const elements = UnsafeCast<FixedDoubleArray>(object.elements);
-      const value = LoadDoubleWithHoleCheck(elements, index) otherwise IfHole;
+      const value = LoadDoubleWithHoleCheck(elements, index) otherwise Bailout;
       return AllocateHeapNumberWithValue(value);
     }
-    label IfHole {
-      return Hole;
+    label Bailout {
+      // The pre-processing step removed all holes by compacting all elements
+      // at the start of the array. Finding a hole means the cmp function or
+      // ToString changes the array.
+      return Failure(sortState);
+    }
+  }
+
+  Load<DictionaryElements>(context: Context, sortState: SortState, index: Smi):
+      Object {
+    try {
+      const object = UnsafeCast<JSObject>(sortState.receiver);
+      const dictionary = UnsafeCast<NumberDictionary>(object.elements);
+      const intptrIndex = Convert<intptr>(index);
+      return BasicLoadNumberDictionaryElement(dictionary, intptrIndex)
+          otherwise Bailout, Bailout;
+    }
+    label Bailout {
+      return Failure(sortState);
     }
   }
 
@@ -248,7 +243,7 @@
     return kSuccess;
   }
 
-  Store<FastSmiElements>(
+  Store<FastPackedSmiElements>(
       context: Context, sortState: SortState, index: Smi, value: Object): Smi {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
@@ -257,7 +252,7 @@
     return kSuccess;
   }
 
-  Store<FastObjectElements>(
+  Store<FastSmiOrObjectElements>(
       context: Context, sortState: SortState, index: Smi, value: Object): Smi {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
@@ -275,42 +270,26 @@
     return kSuccess;
   }
 
-  transitioning builtin Delete<ElementsAccessor: type>(
-      context: Context, sortState: SortState, index: Smi): Smi {
-    const receiver = sortState.receiver;
-    if (!HasProperty_Inline(receiver, index)) return kSuccess;
-    DeleteProperty(receiver, index, kSloppy);
-    return kSuccess;
-  }
-
-  Delete<FastSmiElements>(context: Context, sortState: SortState, index: Smi):
-      Smi {
-    assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind));
-
+  Store<DictionaryElements>(
+      context: Context, sortState: SortState, index: Smi, value: Object): Smi {
     const object = UnsafeCast<JSObject>(sortState.receiver);
-    const elements = UnsafeCast<FixedArray>(object.elements);
-    elements.objects[index] = Hole;
-    return kSuccess;
-  }
-
-  Delete<FastObjectElements>(
-      context: Context, sortState: SortState, index: Smi): Smi {
-    assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind));
-
-    const object = UnsafeCast<JSObject>(sortState.receiver);
-    const elements = UnsafeCast<FixedArray>(object.elements);
-    elements.objects[index] = Hole;
-    return kSuccess;
-  }
-
-  Delete<FastDoubleElements>(
-      context: Context, sortState: SortState, index: Smi): Smi {
-    assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind));
-
-    const object = UnsafeCast<JSObject>(sortState.receiver);
-    const elements = UnsafeCast<FixedDoubleArray>(object.elements);
-    StoreFixedDoubleArrayHoleSmi(elements, index);
-    return kSuccess;
+    const dictionary = UnsafeCast<NumberDictionary>(object.elements);
+    const intptrIndex = Convert<intptr>(index);
+    try {
+      BasicStoreNumberDictionaryElement(dictionary, intptrIndex, value)
+          otherwise Fail, Fail, ReadOnly;
+      return kSuccess;
+    }
+    label ReadOnly {
+      // We cannot write to read-only data properties. Throw the same TypeError
+      // as SetProperty would.
+      const receiver = sortState.receiver;
+      ThrowTypeError(
+          kStrictReadOnlyProperty, index, Typeof(receiver), receiver);
+    }
+    label Fail {
+      return Failure(sortState);
+    }
   }
 
   transitioning builtin SortCompareDefault(
@@ -376,6 +355,12 @@
     return True;
   }
 
+  CanUseSameAccessor<DictionaryElements>(
+      context: Context, receiver: JSReceiver, initialReceiverMap: Object,
+      initialReceiverLength: Number): Boolean {
+    return SelectBooleanConstant(receiver.map == initialReceiverMap);
+  }
+
   // Re-loading the stack-size is done in a few places. The small macro allows
   // for easier invariant checks at all use sites.
   macro GetPendingRunsSize(implicit context: Context)(sortState: SortState):
@@ -434,6 +419,36 @@
     return tempArray;
   }
 
+  // This macro jumps to the Bailout label iff kBailoutStatus is kFailure.
+  macro EnsureSuccess(implicit context: Context)(sortState:
+                                                     SortState) labels Bailout {
+    if (sortState.bailoutStatus == kFailure) goto Bailout;
+  }
+
+  // Sets kBailoutStatus to kFailure and returns kFailure.
+  macro Failure(sortState: SortState): Smi {
+    sortState.bailoutStatus = kFailure;
+    return kFailure;
+  }
+
+  // The following Call* macros wrap builtin calls, making call sites more
+  // readable since we can use labels and do not have to check kBailoutStatus
+  // or the return value.
+
+  macro CallLoad(implicit context: Context, sortState: SortState)(
+      load: LoadFn, index: Smi): Object
+      labels Bailout {
+    const result: Object = load(context, sortState, index);
+    EnsureSuccess(sortState) otherwise Bailout;
+    return result;
+  }
+
+  macro CallStore(implicit context: Context, sortState: SortState)(
+      store: StoreFn, index: Smi, value: Object) labels Bailout {
+    store(context, sortState, index, value);
+    EnsureSuccess(sortState) otherwise Bailout;
+  }
+
   transitioning builtin
   Copy(implicit context: Context)(
       source: FixedArray, srcPos: Smi, target: FixedArray, dstPos: Smi,
@@ -1253,87 +1268,49 @@
   }
 
   transitioning macro
-  CompactReceiverElementsIntoWorkArray(
-      implicit context: Context, sortState: SortState)(): Smi {
-    let growableWorkArray = growable_fixed_array::GrowableFixedArray{
-      array: sortState.workArray,
-      capacity: Convert<intptr>(sortState.workArray.length),
-      length: 0
-    };
+  CopyReceiverElementsToWorkArray(
+      implicit context: Context, sortState: SortState)(length: Smi) {
+    // TODO(szuend): Investigate if we can use COW arrays or a memcpy + range
+    //               barrier to speed this step up.
+    let loadFn = sortState.loadFn;
+    const workArray = sortState.workArray;
 
-    const loadFn = sortState.loadFn;
-
-    // TODO(szuend): Implement full range sorting, not only up to MaxSmi.
-    //               https://crbug.com/v8/7970.
-    const receiverLength: Number = sortState.initialReceiverLength;
-    assert(IsNumberNormalized(receiverLength));
-
-    const sortLength: Smi = TaggedIsSmi(receiverLength) ?
-        UnsafeCast<Smi>(receiverLength) :
-        Convert<PositiveSmi>(kSmiMax) otherwise unreachable;
-
-    // Move all non-undefined elements into {sortState.workArray}, holes
-    // are ignored.
-    let numberOfUndefined: Smi = 0;
-    for (let i: Smi = 0; i < receiverLength; ++i) {
-      const element: Object = loadFn(context, sortState, i);
-
-      if (element == Hole) {
-        // Do nothing for holes. The result is that elements are
-        // compacted at the front of the work array.
-      } else if (element == Undefined) {
-        numberOfUndefined++;
-      } else {
-        growableWorkArray.Push(element);
+    for (let i: Smi = 0; i < length; ++i) {
+      try {
+        workArray.objects[i] = CallLoad(loadFn, i) otherwise Bailout;
+      }
+      label Bailout deferred {
+        sortState.ResetToGenericAccessor();
+        loadFn = sortState.loadFn;
+        workArray.objects[i] = CallLoad(loadFn, i) otherwise unreachable;
       }
     }
-
-    // Reset the workArray on the frameState, as it may have grown.
-    sortState.workArray = growableWorkArray.array;
-    sortState.sortLength = sortLength;
-    sortState.numberOfUndefined = numberOfUndefined;
-
-    return Convert<Smi>(growableWorkArray.length);
   }
 
   transitioning macro
   CopyWorkArrayToReceiver(implicit context: Context, sortState: SortState)(
-      numberOfNonUndefined: Smi) {
-    const storeFn = sortState.storeFn;
+      length: Smi) {
+    // TODO(szuend): Build fast-path that simply installs the work array as the
+    // new backing store where applicable.
+    let storeFn = sortState.storeFn;
     const workArray = sortState.workArray;
 
-    assert(numberOfNonUndefined <= workArray.length);
-    assert(
-        numberOfNonUndefined + sortState.numberOfUndefined <=
-        sortState.sortLength);
-
-    // Writing the elements back is a 3 step process:
-    //   1. Copy the sorted elements from the workarray to the receiver.
-    //   2. Add {nOfUndefined} undefineds to the receiver.
-    //   3. Depending on the backing store either delete properties or
-    //      set them to the Hole up to {sortState.sortLength}.
-    let index: Smi = 0;
-    for (; index < numberOfNonUndefined; ++index) {
-      storeFn(context, sortState, index, workArray.objects[index]);
-    }
-
-    const numberOfUndefinedEnd: Smi =
-        sortState.numberOfUndefined + numberOfNonUndefined;
-    for (; index < numberOfUndefinedEnd; ++index) {
-      storeFn(context, sortState, index, Undefined);
-    }
-
-    const end: Smi = sortState.sortLength;
-    const deleteFn = sortState.deleteFn;
-    for (; index < end; ++index) {
-      deleteFn(context, sortState, index);
+    for (let i: Smi = 0; i < length; ++i) {
+      try {
+        CallStore(storeFn, i, workArray.objects[i]) otherwise Bailout;
+      }
+      label Bailout deferred {
+        sortState.ResetToGenericAccessor();
+        storeFn = sortState.storeFn;
+        CallStore(storeFn, i, workArray.objects[i]) otherwise unreachable;
+      }
     }
   }
 
   transitioning builtin
-  ArrayTimSort(context: Context, sortState: SortState): Object {
-    const numberOfNonUndefined: Smi = CompactReceiverElementsIntoWorkArray();
-    ArrayTimSortImpl(context, sortState, numberOfNonUndefined);
+  ArrayTimSort(context: Context, sortState: SortState, length: Smi): Object {
+    CopyReceiverElementsToWorkArray(length);
+    ArrayTimSortImpl(context, sortState, length);
 
     try {
       // The comparison function or toString might have changed the
@@ -1344,10 +1321,24 @@
       sortState.ResetToGenericAccessor();
     }
 
-    CopyWorkArrayToReceiver(numberOfNonUndefined);
+    CopyWorkArrayToReceiver(length);
     return kSuccess;
   }
 
+  // For compatibility with JSC, we also sort elements inherited from
+  // the prototype chain on non-Array objects.
+  // We do this by copying them to this object and sorting only
+  // own elements. This is not very efficient, but sorting with
+  // inherited elements happens very, very rarely, if at all.
+  // The specification allows "implementation dependent" behavior
+  // if an element on the prototype chain has an element that
+  // might interact with sorting.
+  //
+  // We also move all non-undefined elements to the front of the
+  // array and move the undefineds after that. Holes are removed.
+  // This happens for Array as well as non-Array objects.
+  extern runtime PrepareElementsForSort(Context, Object, Number): Smi;
+
   // https://tc39.github.io/ecma262/#sec-array.prototype.sort
   transitioning javascript builtin
   ArrayPrototypeSort(context: Context, receiver: Object, ...arguments): Object {
@@ -1365,8 +1356,16 @@
 
     if (len < 2) return receiver;
 
-    const sortState: SortState = NewSortState(obj, comparefn, len);
-    ArrayTimSort(context, sortState);
+    // TODO(szuend): Investigate performance tradeoff of skipping this step
+    //               for PACKED_* and handling Undefineds during sorting.
+    const nofNonUndefined: Smi = PrepareElementsForSort(context, obj, len);
+    assert(nofNonUndefined <= len);
+
+    if (nofNonUndefined < 2) return receiver;
+
+    const sortState: SortState =
+        NewSortState(obj, comparefn, len, nofNonUndefined, false);
+    ArrayTimSort(context, sortState, nofNonUndefined);
 
     return receiver;
   }