Bug 53196

Summary: List<>.Sort() using insertion sort does not sort all values when equality isn't checked.
Product: [Mono] Class Libraries Reporter: Jered <jeredmcferron>
Component: mscorlibAssignee: Marek Safar <masafa>
Status: RESOLVED FIXED    
Severity: normal CC: jon.goldberger, masafa, mono-bugs+mono
Priority: ---    
Version: unspecified   
Target Milestone: Untriaged   
Hardware: Macintosh   
OS: Mac OS   
Tags: Is this bug a regression?: ---
Last known good build:
Attachments: Test Project

Description Jered 2017-03-09 16:59:27 UTC
When a list is sorted, the last value in the list is sorted in the wrong order when only doing a "less than" compare.

The specific function used is:
List<>.Sort( delegate( object x, object y ) );


Example:
Input: 1, 3, 5, 2, 6, 6, 6, 6, 6, 6, 6, 7, 4

Sort logic: return x < y ? -1 : 1;

Output: 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 7, 6
(Note that the last value is 6, and should be 7.)

Running this same code built on .NET (in Windows) yields the expected result.

Following is example code that can be compiled on both platforms:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sort
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] array = new int[] { 1, 3, 5, 2, 6, 6, 6, 6, 6, 6, 6, 7, 4 };

			List<int> list = array.ToList();

			list.Sort(delegate (int x, int y)
					   {
						   return x < y ? -1 : 1;
					   });
		}
	}
}
Comment 1 Jon Goldberger [MSFT] 2017-03-16 01:29:49 UTC
Created attachment 20371 [details]
Test Project

I am able to reproduce this behavior and confirm that the behavior is different in Mono than on .NET (Windows). Attached is a simple console app using the code in the bug description.

## Steps to reproduce

1. Open the test project in Xamarin Studio
2. Deploy the console app

Expected result: Elements in list will be sorted in ascending order, i.e. you will see in console output:

> List sorted: True
> 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 7,

Actual result: Last two elements not sorted correctly, i.e. console output shows:

> List sorted: True
> 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 7, 6,

## Notes

Running the same project in Visual Studio yields the expected result.

## Regression status:

Not a regression. Tested back to Mono 4.6.0 and got the same results. 

## Environment

=== Xamarin Studio Enterprise ===

Version 6.2 (build 1829)
Installation UUID: ceaba76c-db06-4fbd-b326-f69ea53c3e01
Runtime:
	Mono 4.8.0 (mono-4.8.0-branch/8f6d0f6) (64-bit)
	GTK+ 2.24.23 (Raleigh theme)

	Package version: 408000520

=== NuGet ===

Version: 3.5.0.0

=== Xamarin.Profiler ===

'/Applications/Xamarin Profiler.app' not found

=== Apple Developer Tools ===

Xcode 8.2.1 (11766.1)
Build 8C1002

=== Xamarin.iOS ===

Version: 10.4.0.128 (Visual Studio Enterprise)
Hash: ba11e48
Branch: cycle9
Build date: 2017-03-10 08:48:04-0500

=== Xamarin.Android ===

Version: 7.1.0.43 (Visual Studio Enterprise)
Android SDK: /Users/jongoldberger/Library/Developer/Xamarin/android-sdk-macosx
	Supported Android versions:
		4.0.3 (API level 15)
		4.1   (API level 16)
		4.2   (API level 17)
		4.3   (API level 18)
		4.4   (API level 19)
		5.0   (API level 21)
		5.1   (API level 22)
		6.0   (API level 23)
		7.0   (API level 24)

SDK Tools Version: 25.2.5
SDK Platform Tools Version: 25.0.3
SDK Build Tools Version: 25.0.2

Java SDK: /usr
java version "1.8.0_91"
Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)

Android Designer EPL code available here:
https://github.com/xamarin/AndroidDesigner.EPL

=== Xamarin Android Player ===

Version: 0.6.5
Location: /Applications/Xamarin Android Player.app

=== Xamarin.Mac ===

Version: 3.0.0.398 (Visual Studio Enterprise)

=== Xamarin Inspector ===

Version: 1.1.2.0
Hash: cdc01b9
Branch: 1.1-release
Build date: Wed, 22 Feb 2017 23:24:11 GMT

=== Build Information ===

Release ID: 602001829
Git revision: 3a28108feb03a6384702c96ffc8c548121cdf37c
Build date: 2017-03-12 06:55:23-04
Xamarin addins: 295d27f8dcdde049a1807a76c888fc0a6557357d
Build lane: monodevelop-lion-cycle9

=== Operating System ===

Mac OS X 10.12.3
Darwin Jons-MacBook-Pro.local 16.4.0 Darwin Kernel Version 16.4.0
    Thu Dec 22 22:53:21 PST 2016
    root:xnu-3789.41.3~3/RELEASE_X86_64 x86_64

=== Enabled user installed addins ===

Addin Maker 1.3.2
Manifest.addin 0.0.0.0
Comment 3 Marek Safar 2017-03-28 07:35:45 UTC
Fixed in master