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

This is a reland of 2b0ac2fb9f355a7a5f2b6470c6357ebf73cfe4cc

The layout test that caused this revert was fixed with:
https://crrev.com/c/1627386

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: jgruber@chromium.org
Bug: v8:8714
Change-Id: If7613f6e5f37c5e0d649e8192195594bc6c32100
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1627977
Commit-Queue: Simon Zünd <szuend@chromium.org>
Auto-Submit: Simon Zünd <szuend@chromium.org>
Reviewed-by: Tobias Tebbi <tebbi@chromium.org>
Cr-Commit-Position: refs/heads/master@{#61827}
diff --git a/src/builtins/base.tq b/src/builtins/base.tq
index cdfb23f..898bffb 100644
--- a/src/builtins/base.tq
+++ b/src/builtins/base.tq
@@ -1024,6 +1024,7 @@
     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 3f7e4f68..a4960cd 100644
--- a/src/debug/debug-evaluate.cc
+++ b/src/debug/debug-evaluate.cc
@@ -263,7 +263,6 @@
   V(HasFastPackedElements)                    \
   V(NewArray)                                 \
   V(NormalizeElements)                        \
-  V(PrepareElementsForSort)                   \
   V(TypedArrayGetBuffer)                      \
   /* Errors */                                \
   V(NewTypeError)                             \
@@ -513,7 +512,6 @@
     case Builtins::kArrayPrototypeKeys:
     case Builtins::kArrayPrototypeLastIndexOf:
     case Builtins::kArrayPrototypeSlice:
-    case Builtins::kArrayPrototypeSort:
     case Builtins::kArrayPrototypeToLocaleString:
     case Builtins::kArrayPrototypeToString:
     case Builtins::kArrayForEach:
@@ -787,6 +785,7 @@
     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 0216767..5896f41 100644
--- a/src/objects/fixed-array.h
+++ b/src/objects/fixed-array.h
@@ -140,8 +140,6 @@
 
   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 2f7e179..3fe98c9 100644
--- a/src/objects/js-objects.cc
+++ b/src/objects/js-objects.cc
@@ -1963,17 +1963,6 @@
                                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 361c74b..b9a7014 100644
--- a/src/objects/js-objects.h
+++ b/src/objects/js-objects.h
@@ -259,9 +259,6 @@
       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 5969435..fece0b5 100644
--- a/src/objects/objects.cc
+++ b/src/objects/objects.cc
@@ -3811,20 +3811,6 @@
   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 a7d10c7..ef5275d 100644
--- a/src/runtime/runtime-array.cc
+++ b/src/runtime/runtime-array.cc
@@ -15,7 +15,6 @@
 #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"
 
@@ -42,386 +41,6 @@
   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 983b64b..2f343bf 100644
--- a/src/runtime/runtime.h
+++ b/src/runtime/runtime.h
@@ -46,7 +46,6 @@
   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 c888972..776d45e 100644
--- a/test/js-perf-test/ArraySort/sort-base.js
+++ b/test/js-perf-test/ArraySort/sort-base.js
@@ -93,7 +93,9 @@
 
 function CreateDictionaryArray() {
   array_to_sort = Array.from(template_array);
-  array_to_sort[%MaxSmi()] = 42;
+  Object.defineProperty(array_to_sort, kArraySize - 2,
+    { get: () => this.foo,
+      set: (v) => this.foo = v });
 
   AssertDictionaryElements();
 }
diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js
index ca0daad..6db8759 100644
--- a/test/mjsunit/array-sort.js
+++ b/test/mjsunit/array-sort.js
@@ -127,9 +127,8 @@
   assertFalse(4 in obj, "objsort non-existing retained");
 }
 
+TestSparseNonArraySorting(1000);
 TestSparseNonArraySorting(5000);
-TestSparseNonArraySorting(500000);
-TestSparseNonArraySorting(Math.pow(2, 31) + 1);
 
 
 function TestArrayLongerLength(length) {
@@ -147,8 +146,7 @@
 TestArrayLongerLength(4);
 TestArrayLongerLength(10);
 TestArrayLongerLength(1000);
-TestArrayLongerLength(500000);
-TestArrayLongerLength(Math.pow(2,32) - 1);
+TestArrayLongerLength(5000);
 
 
 function TestNonArrayLongerLength(length) {
@@ -166,8 +164,7 @@
 TestNonArrayLongerLength(4);
 TestNonArrayLongerLength(10);
 TestNonArrayLongerLength(1000);
-TestNonArrayLongerLength(500000);
-TestNonArrayLongerLength(Math.pow(2,32) - 1);
+TestNonArrayLongerLength(5000);
 
 
 function TestNonArrayWithAccessors() {
diff --git a/test/mjsunit/regress/regress-v8-7682.js b/test/mjsunit/regress/regress-v8-7682.js
index 86f12f5..68f9e0b 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(2, xs[0]);
-assertEquals(1, xs[1]);
+assertEquals(1, xs[0]);
+assertEquals(2, xs[1]);
diff --git a/test/mjsunit/ubsan-fuzzerbugs.js b/test/mjsunit/ubsan-fuzzerbugs.js
index 5a7594d..ae590b6 100644
--- a/test/mjsunit/ubsan-fuzzerbugs.js
+++ b/test/mjsunit/ubsan-fuzzerbugs.js
@@ -72,21 +72,3 @@
   %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 be0180f..216d962 100644
--- a/test/mozilla/mozilla.status
+++ b/test/mozilla/mozilla.status
@@ -163,6 +163,13 @@
   # 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
@@ -509,7 +516,6 @@
   '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 c15c3b6..014155e 100644
--- a/test/webkit/webkit.status
+++ b/test/webkit/webkit.status
@@ -36,6 +36,11 @@
   # 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 ddd796b..8643348 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.bailoutStatus = kSuccess;
+      this.deleteFn = Delete<GenericElementsAccessor>;
     }
 
     // The receiver of the Array.p.sort call.
@@ -54,17 +54,14 @@
     // uses ToString and a lexicographical compare.
     sortComparePtr: CompareBuiltinFn;
 
-    // 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.
+    // 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.
     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.
@@ -90,48 +87,76 @@
 
     // 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, sortLength: Smi,
-      forceGeneric: constexpr bool): SortState {
+      initialReceiverLength: Number): SortState {
     const sortComparePtr =
         comparefn != Undefined ? SortCompareUserFn : SortCompareDefault;
     const map = receiver.map;
-    let loadFn = Load<GenericElementsAccessor>;
-    let storeFn = Store<GenericElementsAccessor>;
-    let canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>;
+    let loadFn: LoadFn;
+    let storeFn: StoreFn;
+    let deleteFn: DeleteFn;
+    let canUseSameAccessorFn: CanUseSameAccessorFn;
 
     try {
-      if constexpr (!forceGeneric) {
-        GotoIfForceSlowPath() otherwise Slow;
-        let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;
+      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>;
-          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>;
-        }
+      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>;
       }
     }
     label Slow {
-      if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
-          !IsCustomElementsReceiverInstanceType(map.instance_type)) {
-        loadFn = Load<DictionaryElements>;
-        storeFn = Store<DictionaryElements>;
-        canUseSameAccessorFn = CanUseSameAccessor<DictionaryElements>;
+      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);
       }
     }
+    label NoJsObject {}
 
     return new SortState{
       receiver,
@@ -141,17 +166,18 @@
       sortComparePtr,
       loadFn,
       storeFn,
+      deleteFn,
       canUseSameAccessorFn,
-      bailoutStatus: kSuccess,
       minGallop: kMinGallopWins,
       pendingRunsSize: 0,
       pendingRuns: AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending)),
-      workArray: AllocateZeroedFixedArray(Convert<intptr>(sortLength)),
-      tempArray: kEmptyFixedArray
+      workArray: AllocateZeroedFixedArray(workArrayLength),
+      tempArray: kEmptyFixedArray,
+      sortLength: 0,
+      numberOfUndefined: 0
     };
   }
 
-  const kFailure: Smi = -1;
   const kSuccess: Smi = 0;
 
   // The maximum number of entries in a SortState's pending-runs stack.
@@ -171,6 +197,7 @@
 
   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;
@@ -183,28 +210,23 @@
 
   transitioning builtin Load<ElementsAccessor: type>(
       context: Context, sortState: SortState, index: Smi): Object {
-    return GetProperty(sortState.receiver, index);
+    const receiver = sortState.receiver;
+    if (!HasProperty_Inline(receiver, index)) return Hole;
+    return GetProperty(receiver, index);
   }
 
-  Load<FastPackedSmiElements>(
-      context: Context, sortState: SortState, index: Smi): Object {
+  Load<FastSmiElements>(context: Context, sortState: SortState, index: Smi):
+      Object {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
     return elements.objects[index];
   }
 
-  Load<FastSmiOrObjectElements>(
-      context: Context, sortState: SortState, index: Smi): Object {
+  Load<FastObjectElements>(context: Context, sortState: SortState, index: Smi):
+      Object {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
-    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;
+    return elements.objects[index];
   }
 
   Load<FastDoubleElements>(context: Context, sortState: SortState, index: Smi):
@@ -212,28 +234,11 @@
     try {
       const object = UnsafeCast<JSObject>(sortState.receiver);
       const elements = UnsafeCast<FixedDoubleArray>(object.elements);
-      const value = LoadDoubleWithHoleCheck(elements, index) otherwise Bailout;
+      const value = LoadDoubleWithHoleCheck(elements, index) otherwise IfHole;
       return AllocateHeapNumberWithValue(value);
     }
-    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);
+    label IfHole {
+      return Hole;
     }
   }
 
@@ -243,7 +248,7 @@
     return kSuccess;
   }
 
-  Store<FastPackedSmiElements>(
+  Store<FastSmiElements>(
       context: Context, sortState: SortState, index: Smi, value: Object): Smi {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
@@ -252,7 +257,7 @@
     return kSuccess;
   }
 
-  Store<FastSmiOrObjectElements>(
+  Store<FastObjectElements>(
       context: Context, sortState: SortState, index: Smi, value: Object): Smi {
     const object = UnsafeCast<JSObject>(sortState.receiver);
     const elements = UnsafeCast<FixedArray>(object.elements);
@@ -270,26 +275,42 @@
     return kSuccess;
   }
 
-  Store<DictionaryElements>(
-      context: Context, sortState: SortState, index: Smi, value: Object): Smi {
+  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));
+
     const object = UnsafeCast<JSObject>(sortState.receiver);
-    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);
-    }
+    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;
   }
 
   transitioning builtin SortCompareDefault(
@@ -355,12 +376,6 @@
     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):
@@ -419,36 +434,6 @@
     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,
@@ -1268,49 +1253,87 @@
   }
 
   transitioning macro
-  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;
+  CompactReceiverElementsIntoWorkArray(
+      implicit context: Context, sortState: SortState)(): Smi {
+    let growableWorkArray = growable_fixed_array::GrowableFixedArray{
+      array: sortState.workArray,
+      capacity: Convert<intptr>(sortState.workArray.length),
+      length: 0
+    };
 
-    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;
+    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);
       }
     }
+
+    // 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)(
-      length: Smi) {
-    // TODO(szuend): Build fast-path that simply installs the work array as the
-    // new backing store where applicable.
-    let storeFn = sortState.storeFn;
+      numberOfNonUndefined: Smi) {
+    const storeFn = sortState.storeFn;
     const workArray = sortState.workArray;
 
-    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;
-      }
+    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);
     }
   }
 
   transitioning builtin
-  ArrayTimSort(context: Context, sortState: SortState, length: Smi): Object {
-    CopyReceiverElementsToWorkArray(length);
-    ArrayTimSortImpl(context, sortState, length);
+  ArrayTimSort(context: Context, sortState: SortState): Object {
+    const numberOfNonUndefined: Smi = CompactReceiverElementsIntoWorkArray();
+    ArrayTimSortImpl(context, sortState, numberOfNonUndefined);
 
     try {
       // The comparison function or toString might have changed the
@@ -1321,24 +1344,10 @@
       sortState.ResetToGenericAccessor();
     }
 
-    CopyWorkArrayToReceiver(length);
+    CopyWorkArrayToReceiver(numberOfNonUndefined);
     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 {
@@ -1356,16 +1365,8 @@
 
     if (len < 2) return receiver;
 
-    // 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);
+    const sortState: SortState = NewSortState(obj, comparefn, len);
+    ArrayTimSort(context, sortState);
 
     return receiver;
   }